CS Paper Radar

An Integrality-Gap Lower Bound of 1.2325 for Minimum Multiway Cut

Dimitar Chakarov, Yury Makarychev

cs.DS ·submitted 2026-11-03 22:49 UTC · v1
theoryhot direction

Abstract

We prove that the integrality gap of the Călinescu-Karloff-Rabani relaxation for Minimum Multiway Cut is at least $1.2325$ when the number of terminals is large. By a result of Manokaran, Naor, Raghavendra, and Schwartz (2008), it is therefore NP-hard, under the Unique Games Conjecture, to approximate Minimum Multiway Cut within a factor of $1.2325$. This improves the previously best known lower bound of $1.20016$ due to Bérczi, Chandrasekaran, Király, and Madan (2020).

Comment
37 pages, 2 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Improved lower bounds on the approximability of Multiway Cut using Sherali-Adams relaxations

cs.DS cs.CC ·2026-11-03 ·Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick
theory similarity 0.81
Abstract · 66 pages

The Multiway Cut problem is among the most well-studied problems in the area of combinatorial approximation algorithms. The currently best approximation ratio for the problem is 1.2787, obtained recently by the authors (2026). The best lower bound on the approximation ratio that can be achieved for the problem in polynomial time, under the Unique Games Conjecture (UGC), is 1.20016, obtained by Bérczi, Chandrasekaran, Király, and Madan (2020), building on and slightly improving a bound of $\frac65=1.2$, obtained by Angelidakis, Makarychev, and Manurangsi (2017) by introducing the important framework of non-opposite multiway cuts. We obtain a substantially improved lower bound of 1.22232 on the approximation ratio of the Multiway Cut problem. Manokaran, Naor, Raghavendra, and Schwartz (2008) showed that under UGC, the approximation ratio of Multiway Cut is equal to the integrality ratio of a simple LP relaxation, known as the CKR relaxation, introduced by Călinescu, Karloff, and Rabani (2000). Thus, stronger LP relaxations are not required for obtaining an optimal approximation algorithm for the problem. We show, however, that relying on the framework of Angelidakis, Makarychev, and Manurangsi (2017), stronger LP relaxations from the Sherali-Adams hierarchy for non-opposite multiway cuts can be used to obtain improved integrality ratios for the CKR relaxation, and hence improved lower bounds on the approximation ratio of the Multiway Cut problem. One of the novel features of our analysis is considering a continuous limit of discrete LPs defined on a simplex. Our proof of the new 1.22232 bound is completely analytic. We also present strong numerical evidence that suggests that our techniques can be used to improve the lower bound to at least 1.23003.

0.32

Remote Matching: Exact-Cardinality Approximation and Tight UGC Hardness

cs.DS ·2026-09-22 ·Arash Ahadi, Morteza Alimi, Sharareh Alipour, Shayan Tayefeh
similarity 0.67
Abstract

In the unrestricted max--min metric $T$-join problem, one seeks an even terminal set $T$ maximizing the cost of a minimum $T$-join. Iwata and Ravi gave a factor-$3/2$ approximation for this problem. We show that this guarantee is tight under the Unique Games Conjecture: no polynomial-time approximation with factor strictly smaller than $3/2$ exists under UGC. We then consider the exact-cardinality variant, which prescribes an even number \(k\) of terminals. Writing \(p:=k/n\), we give a deterministic polynomial-time \(ρ(p)\)-approximation for every feasible cardinality, where \[ ρ(p)= \begin{cases} 7/2, & \makebox[1.5em][r]{$0$}<p\le2/7,\\ 1/p, & 2/7\le p\le2/3,\\ 1/[2(1-p)], & 2/3\le p\le7/8,\\ 4, & 7/8\le p<1. \end{cases} \] In particular, a factor-\(4\) approximation holds throughout the entire feasible cardinality range, the factor is at most \(7/2\) whenever \(0<k\le 6n/7\), and equals \(3/2\) at \(k=2n/3\). The algorithmic framework is based on optimal laminar cut packings, their weighted tree representations, exact-cardinality rounding, and tree dynamic programming.

0.13

Quasi-polynomial-sized vertex multicut-mimicking networks and kernelization for Vertex Multiway Cut

cs.DS ·2026-11-05 ·Eduard Eiben, Roohani Sharma, Magnus Wahlström
survey similarity 0.64
Abstract

We give deterministic polynomial-time constructions of vertex multicut-mimicking networks of quasi-polynomial size. Given a graph G, a terminal set T, and a positive integer c, our algorithm constructs a graph with |T|^7 c^{O( log c ) } vertices that preserves every minimum vertex multiway cut value of at most c, for every partition of the terminals. Setting c=|T| gives an exact vertex multicut-mimicking network with |T|^{O( log |T| ) } vertices, resolving an open question of Wahlström [ACM Transactions on Algorithms 2022], who showed a bound of κ^{O( log^3 κ)} for the edge multicut-mimicking variant, where κ:= \sum_{t \in T} |N_G(t)| is the capacity of the terminal set, which was later improved to κ^{O( log^2 κ)} by Anand, Lee, Li and Saranurak [STOC 2024]. As applications of our vertex multicut-mimicking network, we obtain deterministic kernels of size k^{O( log k )} for Vertex Multiway Cut, p^{O(1)} k^{O(log k)} for Vertex Multicut with p requests and |Γ|^{O(1)} k^{O( log k)} for Group Feedback Vertex Set, where k is the deletion budget and Γis a finite group. Our first kernelization result, in particular, resolves an open question by Wahlström [ACM Transactions on Algorithms 2022], which was reiterated in a recent survey on kernelization by Jansen [Computer Science Reviews 2026]. Also, to the best of our knowledge, our kernel for Vertex Multicut is the first one whose size is completely polynomial in p and (quasi-polynomial) super-polynomial only in k. Finally, again using our vertex multicut-mimicking network for graphs, we obtain a hyperedge multicut-mimicking network for hypergraphs, which preserves hypergraph edge-multicuts of size up to c, of size |T|^{O(1)} c^{O(log c)}. Our result removes the dependence on the rank of the hypergraph from the exponent of the size bound, that existed in prior work.

0.29

Improved Integrality Gap for Multicommodity Flow on Trees

cs.DS math.CO ·2026-09-07 ·Elfarouk Harb
theory similarity 0.62
Abstract · 11 pages

We improve the best known lower bound on the integrality gap for weighted unit-demand multicommodity flow on trees from $1/4$ to $2/5$, improving on the long-standing bound of Chekuri, Mydlarz, and Shepherd~\cite{CMS}. We give the proof in two stages. First, a surprisingly simple packing lemma and an inductive coloring argument give an intermediate bound of $4/11$. We then refine the argument to obtain $2/5$.

0.28

On the Communication Complexity of Shortcut Set Computation

cs.DS ·2026-11-06 ·Gregory Bodwin, Luba Samborska
theory similarity 0.61
Abstract

A recent breakthrough of Kogan and Parter (SODA '22) provided the first polynomial improvement in decades on the size/diameter tradeoff available for shortcut sets. However, algorithmic applications of shortcut sets have mostly not taken advantage of these new bounds. A barrier is that many shortcut set applications occur in \emph{decentralized} settings, and we generally lack decentralized algorithms implementing the Kogan-Parter bounds. To this end, we study the \emph{communication complexity} of constructing Kogan-Parter shortcut sets. The edges of an $n$-node directed graph are split between two players, Alice and Bob, who are also given a target diameter $D$. Our main result is a protocol that, for $D \le n^{1/3}$, allows Alice and Bob to agree on a shortcut set matching the Kogan-Parter tradeoff between size and diameter, while exchanging only $\Oish(n^2 / D^2)$ bits of communication. We also provide (non-matching) lower bounds on the communication complexity required to find a correct $D$-diameter shortcut set of any size. The main technical ingredient for the upper bounds is a low-communication protocol for finding a \emph{path cover}, a common subroutine in shortcut set constructions that has attracted some independent interest. Our protocol crucially avoids applications of Menger's theorem or antichain decompositions, as often done in prior work. On the lower bounds side, we relate the communication complexity of the shortcut set problem to the size of bridge-free path systems.

0.23

Improved NP-Hardness of Approximation for Max-3-Cut and for Max-k-Cut with Small k

cs.CC ·2026-11-01 ·Ziang Ni
theorycode/data similarity 0.61
Abstract · 20 pages, 5 figures. Code, gadget families and certificates: https://github.com/ziangni-sys/max-3-cut

We prove that Max-3-Cut is NP-hard to approximate within a factor of $27/29+\varepsilon \approx 0.931$. This improves the factor $16/17 \approx 0.941$ of Austrin, O'Donnell, Tan and Wright, the best NP-hardness result for Max-3-Cut since 2012. (Their result, unlike ours, also holds for 3-colourable graphs.) We also improve the NP-hardness of Max-$k$-Cut for every $k$ from 4 to 20; for instance, we obtain $45/47 \approx 0.957$ for Max-4-Cut and $33/34 \approx 0.971$ for Max-5-Cut, where the previous factors were 0.987 and 120/121. Our reductions are gadget reductions from Håstad's linear equations over $\mathbb{Z}_3$, with gadgets that have at most six auxiliary vertices. The main new idea is a negation trick: since the negation of an assignment is again an assignment, equations with right-hand sides $t$ and $-t$ can be handled together, and this makes the resulting predicates symmetric under all permutations of the colours. We complement it with a general soundness criterion for such reductions: in effect, the best strategy of the adversary is to use a single colour pattern everywhere. This criterion is the strongest analysis that uses Håstad's theorem as a black box, and, using LP duality, we show that under it no gadget reduction from these equations can beat $27/29$ for Max-3-Cut. Finally, we observe that a classical reduction from Max-3-Cut to Max-$k$-Cut, applied more carefully, already gives $82/85 \approx 0.965$ for Max-4-Cut on 4-colourable graphs, improving the previously stated $85/86$.

0.47

Integrality Gap of 3.4 for Santa Claus: A Topology-based Analysis

cs.DS cs.DM ·2026-11-11 ·Kimon Boehmer, Chien-Chung Huang
theory similarity 0.60
Abstract

In the \textsc{Max-Min Allocation} problem, a set of indivisible items are to be assigned to a set of players and the goal is to maximize the minimum value among all players. A much studied special case, the \textsc{Santa Claus} problem, assumes that an item has a fixed utility but a player is only interested in a subset of items. The main technique for designing approximation algorithms for \textsc{Santa Claus} is the configuration LP, introduced by the Bansal and Sviridenko. A long line of research has progressively improved the upper bound of the integrality gap, mostly relying on the combinatorial arguments of Haxell for finding perfect matchings in certain hypergraphs. Remarkably, a recent paper of Haxell and Szabó (SODA '23) introduced a novel topology-based analysis, by which they are able to obtain the current best upper bound of $3.534$. In this work, we adapt the approach of Haxell and Szabó to analyze the integrality gap. The main new ingredient in our adaptation is that we stop the process of "edge explosions" in a graph used by Haxell and Szabó when it becomes too costly. This early termination of explosions, combined with a new lower bound on a topological connectivity parameter based on a theorem of Aharoni, Berger, and Meshulam, allows us to improve the integrality gap to $3.4$. Our analysis has the additional advantage of being simpler.

0.28

Optimal Algorithms and Hardness for Max-Cut in Bounded Degree Graphs

cs.DS ·2026-10-19 ·Rares-Darius Buhai, Suprovat Ghoshal, Neng Huang, Pravesh Kothari, Euiwoong Lee +2 more
theory similarity 0.59
Abstract · 70 Pages

We give a polynomial-time algorithm that achieves an $α_{GW} + \tildeΩ(1/d)$-approximation for Max 2-LIN(2) in weighted instances where each vertex appears in at most $d$ constraints. This improves on the $α_{GW}+\tildeΩ(1/d^2)$-approximation guarantee of [Hsieh-Kothari, ICALP'23]. We also show a matching Unique Games hardness under randomized polynomial-time reductions, thereby proving that the gain on $α_{GW}$ is optimal up to $\mathrm{polylog}(d)$ factors. Here, $α_{GW} \approx 0.878$ is the approximation ratio of the Goemans-Williamson algorithm. Our results resolve an open question due to Raghavendra and refute his conjectured optimal approximation ratio of $α_{GW} + \tildeΩ(1/\sqrt{d})$. Our local improvement scheme can be thought of as using an adaptive (based on the neighbors) shift applied to the Gaussian before using the GW sign rounding. This allows us to implement a ``soft but simultaneous'' flipping decision at each vertex as opposed to hard but sequential flipping decisions in prior works. Our hardness results are based on a new sparsification lemma for graphs produced by the reduction from Unique Games [Khot-Kindler-Mossel-O'Donnell, SICOMP'07] that preserves the optimal values up to a factor of $1 \pm ε$ while subsampling to an average degree of only $\tilde{O}(1/ε)$. This is the first example of a CSP in which the optimal advantage on degree-$d$ instances is asymptotically smaller than $O(1/\sqrt{d})$ [Trevisan, STOC'01]. A key idea in the proof of our sparsification theorem establishes new bounds on the number of ``nearly optimal'' cuts in the output of the KKMO reduction. This step, in turn, relies on a new, robust inverse Majority-Is-Stablest theorem.

0.15