CS Paper Radar

Multiway Partition is FPT for Connectivity Functions

Tony Huynh, Eun Jung Kim, Sang-il Oum, Roohani Sharma, Marek Sokołowski

cs.DM math.CO ·submitted 2026-08-11 02:21 UTC · v2
theory

Abstract

Let $E$ be a set of $n$ elements, $f\colon2^E\to\mathbb Z_{\ge0}$ be submodular, $t_1,\ldots,t_r\in E$ be distinct, and $k\in\mathbb N$. The Submodular Multiway Partition problem asks whether $E$ has a partition $(P_1,\ldots,P_r)$ with $t_i\in P_i$ for all $i$ and $\sum_i f(P_i)\le k$. We prove that this problem can be solved in $r^{O(k)}n^{O(1)}$ time whenever $f$ is posimodular. This covers monotone submodular functions, matroid rank functions, and nonnegative combinations of monotone and symmetric submodular functions. When $f$ is a connectivity function, we remove the dependence on the number of terminals and obtain a $k^{O(k)}n^{O(1)}$-time algorithm. The proof is entirely elementary, and is arguably the simplest proof that Edge Multiway Cut is fixed-parameter tractable. As a new consequence, our main result immediately implies that Hypergraph Multiway Partition is fixed-parameter tractable.

Comment
New title and strengthened main theorem that only needs posimodularity. Application to Hypergraph Multiway Partition is also added. 9 Pages, 0 Figures

Closest papers

Nearest neighbours by meaning across the whole index.

An $O(k\log(n/k))$ Bound on Spanning Bipartite Connectivity

cs.DM math.CO ·2026-09-20 ·G. Gutin, Y. Hao, Y. Zhou
theory similarity 0.63
Abstract · All proofs were written by the authors without the assistance of AI. However, GPT-6 Astra was used to check the correctness of our proofs, a…

For integers $1\le k\le n/2$, let $f(k,n)$ be the least integer $s$ such that every $s$-connected graph on $n$ vertices contains a spanning bipartite $k$-connected subgraph. Thomassen conjectured that $f(k,n)$ is bounded by a function of $k$ alone. Delcourt and Ferber proved $f(k,n)=O(k^3\log n)$, and Yuster subsequently obtained $f(k,n)\le22k^2\log_2 n$. We prove that, for $2\le k\le n/2$, \[ f(k,n)\le\min\left\{n-1,\, \left\lfloor6(k-1)\log_2\frac{n}{k-1}\right\rfloor\right\}. \] In particular, $f(k,n)=O(k\log(n/k))$.

0.33

Universal set families for maximization of nonnegative submodular and XOS functions

cs.DS ·2026-09-17 ·Chandra Chekuri, Richard Ueltzen, Jan Vondrak
theoryhot direction similarity 0.61
Abstract · The main results were obtained with ChatGPT-5.6 Sol

We consider the question of designing a universal family of sets $F \subset 2^{[n]}$ such that for any function $f:2^{[n]} \to R_{\geq 0}$ in a certain class, we have $$\max_{S \in F} f(S) \geq c(n) \cdot \max_{S \subset [n]} f(S).$$ We prove that there is a family of subpolynomial size such that for any nonnegative submodular function, $c(n) = Ω(\frac{\log \log n}{\log n})$, and there is a family of logarithmic size such that $c(n) = Ω(\frac{1}{\log n})$. We also prove that pairwise independence (which achieves a constant factor for graph cut functions), or even $k$-wise independence, does not imply a bound better than $O(\frac{1}{\sqrt{\log n}})$ for submodular functions. On the other hand, we prove that for any polynomially representable subclass of nonnegative submodular functions (such as the matroid connectivity functions for matroid representable over $F_q$), a constant-factor universal family of polynomial size always exists. For absolute XOS functions (a class that we introduce, in the form $f(S) = \max_i |\sum_{j \in S} w_{ij} + c_i|$ where $w_{ij}, c_i \in R$), we design a family of polynomial size such that $c(n) \geq \sqrt{\frac{\log n}{n}}$, and prove that there is no polynomial-size family achieving a factor better than $O(\sqrt{\frac{\log n}{n}})$.

0.33

A Polynomial Time Algorithm for Finding a Minimum 5-Partition of a Submodular Function

cs.DS math.CO ·2026-11-16 ·Yuhao Liu, Ke Shi, Chao Xu
similarity 0.59
Abstract · 11 pages

Given a real-valued submodular function on a finite ground set, the minimum $k$-partition problem asks for a partition into $k$ nonempty parts minimizing the sum of their function values. We give a polynomial-time algorithm for $k=5$. The idea follows directly from the previous $k=4$ result, where there is precisely one obstruction for generalizing it to $k=5$. We show the special case can be handled by reasoning about a restricted family of $3$-partitions.

0.43

Randomized Lifting for One-Way Number-on-Forehead Communication

cs.CC ·2026-09-26 ·Chenyu Wang
theory similarity 0.57
Abstract

We prove a lifting theorem from two-party public-coin one-way communication to multiparty public-coin one-way number-on-forehead (NOF) communication. For every fixed $k\ge2$ and prime $q>2k$, there is a generalized inner product gadget $\GIP_{q,r}^k:(\F_q^r)^k\to\F_q$ with $r=O_k(q/\log q)$ such that, for every partial Boolean function $f:D\to\bits$, where $D\subseteq\F_q\times\F_q$, \[ R_{1/3}^1(f)-O(1) \le R_{1/6}^{1,\NOF}\bigl(f\circ\GIP_{q,r}^k\bigr) \le R_{1/6}^1(f). \] Thus, composition with the gadget preserves one-way randomized communication complexity up to an additive constant and a change in the error parameter. The lower bound holds in the general one-way NOF model, where the last player sees the entire gadget input. This extends the deterministic one-way NOF lifting theorem of Yang and Zhang to randomized protocols, and extends the randomized lifting result of Wang and Wu from the conservative model to the general one-way NOF model. Our proof introduces a one-way cylinder partition bound that lower bounds public-coin one-way NOF communication complexity. We show that, for the lifted function, this bound is at least half the one-way partition bound of the outer function. The main technical step transfers a dual solution between the two bounds, using Möbius inversion and a discrepancy estimate for generalized inner product to control the loss. Combining this transfer with the characterization of two-party one-way randomized communication complexity by the one-way partition bound yields the lifting theorem.

0.29

All minimum cuts of symmetric submodular functions

cs.DS math.COmath.OC ·2026-11-05 ·Chao Xu
hot direction similarity 0.57
Abstract

We compute Cunningham's canonical decomposition of a symmetric submodular function on $n$ elements in $O(n^3)$ time. The decomposition represents all minimum cuts in linear space. For the pair $s,t$ produced by Queyranne's algorithm, we construct in $O(n^2)$ time a digraph representing exactly the minimum $st$-cuts of the function. Using this construction in Chekuri and Xu's decomposition algorithm gives the cubic bound.

0.26

NP-hardness of additive approximation for generalized Turán problems

cs.CC math.CO ·2026-10-12 ·Yihan Chen, Jialin He, Xihe Li, Jie Ma, Tianying Xie
similarity 0.56
Abstract · 34 pages, 0 figures

Given a graph $T$ and a nonempty family $\mathcal{F}$ of graphs, let $\operatorname{ex}(G, T, \mathcal{F})$ denote the maximum number of copies of $T$ in an $\mathcal{F}$-free subgraph of a host graph $G$. Alon and Shikhelman [Algorithmica, 2022] conjectured that if $e(T)> 0$ and no member of $\mathcal{F}$ is a subgraph of a blow-up of $T$, then for every $\varepsilon>0$, approximating $\operatorname{ex}(G, T, \mathcal{F})$ within an additive error of $n^{v(T)-\varepsilon}$ is NP-hard for an input graph $G$ on $n$ vertices. Previous advances toward this conjecture include the resolution of the canonical case $T=K_2$ by Alon, Shapira, and Sudakov [Ann. of Math., 2009], as well as the case of $\operatorname{ex}(G,K_m,K_k)$ by Alon and Shikhelman. In this paper, we confirm this conjecture for every bipartite graph $T$ and every clique $T$. Our proof reductions combine several techniques, including iterative leaf additions, symmetric rooted extensions, and random transversals. Together, they encode the optimal value of the NP-hard Max $r$-Colorable Subgraph problem into the objectives $\operatorname{ex}(G, T, \mathcal{F})$ for a suitably constructed graph $G$.

0.40

Polynomial directed treewidth forces a large bramble with congestion two

cs.DS cs.DMmath.CO ·2026-10-09 ·Victor A. Campos, Raul Lopes, Rodrigo Nogueira, Ignasi Sau
theory similarity 0.56
Abstract

Brambles of constant congestion in directed graphs have interesting structural and algorithmic applications, and it is desirable to find the smallest function $f_c(k)$ such that if a digraph has directed treewidth at least $f_c(k)$, then it contains a bramble of size at least $k$ and congestion at most $c$. By the Directed Grid Theorem of Kawarabayashi and Kreutzer [STOC 2015], such a function $f_c(k)$ exists for every value $c \geq 2$ of the congestion. However, even using the recent improvements due to Hatzel et al. [FOCS 2024], the resulting function is a power tower of height $22$. Recently, Masařík et al. [SIAM J. Discrete Math. 2022] proved that, for congestion $8$, the function $f_8(k)$ can be made polynomial; more precisely, they showed that $f_8(k) = \mathcal{O}(k^{48} \cdot \log^{13} k)$. They asked whether it is possible to decrease the congestion, ideally to $2$, even at the cost of a higher polynomial function. In this work we answer their question affirmatively with the best possible value of the congestion, by proving that $f_2(k) = \mathcal{O}(k^{96}\cdot \log^{23} k)$. We also obtain smaller polynomials for higher congestion, namely $f_4(k) = \mathcal{O}(k^{72} \cdot \log^{21} k)$ and $f_6(k) = \mathcal{O}(k^{66} \cdot \log^{18} k)$. Our results are inspired by the proof for congestion $8$, which we improve by introducing walkages. Walkages allow us to avoid technicalities of the original proof by translating ideas due to Reed and Wood [Eur. J. Comb. 2012] that work for undirected graphs to the directed setting. Our proofs are constructive and naturally yield polynomial-time algorithms to find the brambles assuming a certificate for large directed treewidth is given. Moreover, we discuss algorithmic applications of our results for the Directed Disjoint Paths with Congestion problem, and to half-integral packings of subgraphs with large directed treewidth.

0.29

A rainbow partition theorem for trees and connected maximin share allocations of chores

cs.DM math.COecon.THmath.OC ·2026-09-29 ·Marcin Anholcer, Maciej Bartkowiak, Bartłomiej Bosek, Jarosław Grytczuk, Zbigniew Lonc +1 more
theory similarity 0.56
Abstract

Xiao, Qiu, and Huang (AAMAS 2023) and independently Lonc (personal communication) asked whether indivisible chores located at the vertices of a tree can always be allocated to $n$ agents in connected bundles so that the cost of every agent is at most its connected maximin share; for goods, this is a theorem of Bouveret, Cechlárová, Elkind, Igarashi, and Peters. We answer the question affirmatively, even for monotone costs. The answer follows from a combinatorial theorem: if $\mathcal P_1,\ldots,\mathcal P_k$ are partitions of the vertex set of a finite tree, each into at most $k$ connected parts, then the vertex set can be split into disjoint sets $B_1,\ldots,B_k$, some possibly empty, such that each nonempty $B_i$ is connected and contained in a part of $\mathcal P_i$. Equivalently, if each of $k$ colours occurs on at most $k-1$ edges of a tree, then the vertices can be partitioned into connected sets labelled by distinct colours, none containing an edge of its own colour; in particular, one can choose for every colour a component of the forest obtained by deleting that colour so that the chosen components cover the tree. The bound is already best possible for paths, and for additive costs, the theorem is equivalent to the fair-division statement. The proof reduces the problem to inward partitions of oriented trees, which we obtain from the colourful KKM theorem on a simplex of edge weights, using a leaf-elimination labelling that remains compatible when weights vanish. We also give an algorithm running in time $k^{O(k)}$ plus polynomial time.

0.35