Source-linked AI summary
On Multiway Cut parameterized above lower bounds
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk
TL;DR
Separating multiple terminals makes Node Multiway Cut hard, motivating parameterizations above lower bounds. The paper proves fixed-parameter algorithms for two such bounds, yielding improved running times for standard Node Multiway Cut and related problems.
Problem
Separating three or more terminals makes Node Multiway Cut hard: deciding the minimum cut for three terminals is NP-hard.
Source: §1 · p. 1Method
The paper parameterizes Node Multiway Cut by the gap above the largest isolating cut or the optimal LP-relaxation cost, then gives fixed-parameter algorithms.
Source: §1 · p. 2Results
O*(4^L(I)) time above the LP bound and O*(2^C(I)) above the maximum separating cut yield an O*(2^k) standard Node Multiway Cut algorithm.
Source: §1 · pp. 2–3Takeaways & Limitations
The results also give O*(4^k) algorithms for Vertex Cover above Maximum Matching and Almost 2-SAT.
Source: §1 · p. 3Node Multicut above its natural LP relaxation is not in XP; whether the edge-deletion variant is similarly difficult remains open.
Source: §5 · p. 8
Abstract
from arXiv · showhide
In this paper we consider two above lower bound parameterizations of the Node Multiway Cut problem - above the maximum separating cut and above a natural LP-relaxation - and prove them to be fixed-parameter tractable. Our results imply O*(4^k) algorithms for Vertex Cover above Maximum Matching and Almost 2-SAT as well as an O*(2^k) algorithm for Node Multiway Cut with a standard parameterization by the solution size, improving previous bounds for these problems.
1 Introduction
Node Multiway Cut becomes NP-hard with multiple terminals, motivating algorithms parameterized by the gap above lower bounds rather than solution size alone. The paper establishes fixed-parameter algorithms for two such bounds and derives improved results for related problems.
1 Introduction
- Above-guaranteed-value parameterization uses the difference between the solution size and a lower bound, which can help when that bound is large.The paper considers the largest isolating cut and the optimal LP-relaxation cost as lower bounds for Node Multiway Cut.Source: §1 · p. 2
- The optimal LP-relaxation cost is a lower bound on the minimum cut size, and each terminal's minimum isolating cut is also such a lower bound.The LP has exponentially many constraints but can be solved in polynomial time; isolating-cut values are computable using standard max-flow techniques.Source: §1 · p. 2
- O*(4^L(I)) time above the LP lower bound and O*(2^C(I)) time above the maximum separating cut make both Node Multiway Cut parameterizations fixed-parameter tractable.The two parameters are L(I) = k − LP(I) and C(I) = k − max_t∈T m(I,t).Source: §1 · p. 2
- O*(2^k) time solves standard Node Multiway Cut, improving the previous O*(4^k) bound.The algorithm follows because an instance with C(I) > k is trivially negative.Source: §1 · p. 3
- The results also hold for edge-deletion Multiway Cut, which is easier than the node-deletion variant.FPT for edge-deletion Multiway Cut above maximum separating cut was implicit in Xiao.Source: §1 · p. 3
- O*(4^k) algorithms for Vertex Cover above Maximum Matching and Almost 2-SAT improve the previous O*(15^k) bound.Vertex Cover above Maximum Matching is a special case of NMWC-a-LP, and it is equivalent to Almost 2-SAT from the perspective of parameterized complexity [18].Source: §1 · p. 3
- The algorithm reduces the number of terminals to 2k in polynomial time, improving a previous quadratic bound.The paper also gives polynomial-time reduction rules relevant to the open question of a polynomial kernel for solution-size parameterized Node Multiway Cut.Source: §1 · p. 3
- Node Multicut, a generalization of Node Multiway Cut, is not in XP when parameterized above its natural LP relaxation.Node Multicut was known to be FPT when parameterized by solution size [14] [1].Source: §1 · p. 3
2 Algorithms for Multiway Cut
The section gives an LP-based branching algorithm for Node Multiway Cut and derives running-time bounds above two lower bounds. It also establishes a terminal-count reduction bound after polynomial-time rules.
2 Algorithms for Multiway Cut
- The authors construct another optimal solution to LP-relaxation (1): set d_v=1 when v neighbors zero areas of at least two terminals, 1/2 for exactly one, and 0 otherwise.Source: §2 · p. 3
- After Reductions 1–3, setting d_v=1/2 on N(T) and 0 elsewhere is LP-optimal, and each N(t) is t’s unique minimum separating cut.These structural properties support the branching analysis and the parameter bounds.Source: §2 · p. 4
- O*(4^L(I)) time solves Node Multiway Cut when parameterized above the LP-relaxation.The algorithm uses polynomial-time reductions followed by two branches, each decreasing L(I) by at least 1/2; a branch rejects when L(I) becomes negative.Source: §2 · pp. 3–5
- There exists an algorithm solving Node Multiway Cut instance I in O*(2^min(C(I), ((s−2)/(s−1))·k)) time, yielding O*(2^(k/2)) time when there are three terminals.Source: §2 · p. 5
- If Reductions 1, 2, 3, and 5 do not apply, the number of terminals is at most 2k.The paper presents these polynomial-time reductions as potentially useful for kernelization.Source: §2 · p. 5
3 From Node Multiway Cut to Almost 2-SAT
The section transfers the Node Multiway Cut algorithm to Vertex Cover above Maximum Matching and then to Almost 2-SAT. Both problems receive O*(4^k)-time algorithms through these reductions.
3 From Node Multiway Cut to Almost 2-SAT
- O*(4^k)-time algorithms solve both Vertex Cover above Maximum Matching and Almost 2-SAT.The Vertex Cover result follows from its reduction to Node Multiway Cut above the LP-relaxation; the Almost 2-SAT result follows through Vertex Cover above Maximum Matching.Source: §3 · pp. 6–7
- A Vertex Cover instance becomes a Node Multiway Cut instance with k′=µ(G)+k and LP(I′)≥µ(G), so L(I′)≤k.The construction adds a degree-one terminal for each original vertex; a vertex cover corresponds to deleting vertices so each remaining component contains at most one terminal.Source: §3 · p. 6
- The Almost 2-SAT reduction creates literal-occurrence vertices, variable-wise complete bipartite edges, and one clause edge per clause, preserving YES-instances.The paper proves equivalence between deleting at most k clauses to make the formula satisfiable and finding a vertex cover of size at most µ(G)+k.Source: §3 · pp. 6–7
4 Hardness of Node Multicut parameterized above LP-relaxation
The section proves that Node Multicut parameterized above its natural LP-relaxation is not in XP, by showing NP-hardness even when the parameter is zero.
4 Hardness of Node Multicut parameterized above LP-relaxation
- NMC-a-LP is NP-hard even on instances with L(I)=0, and therefore is not in XP.The parameter is the solution budget minus the optimal LP-relaxation cost.Source: §4 · p. 7
- The hardness reduction starts from Multicoloured Independent Set and builds a Node Multicut instance with budget n from the partitioned graph.The construction adds a copy vertex for each original vertex, connects copies within each color class into paths, and introduces terminal pairs.Source: §4 · p. 7
- The constructed instance has LP optimum n, and a Node Multicut solution of size n exists exactly when the source graph has an independent set selecting one vertex per class.The proof translates such an independent set into a solution and derives the reverse implication from any size-n solution.Source: §4 · p. 8
5 Conclusions
The conclusions recap fixed-parameter tractability for Node Multiway Cut above two lower bounds and highlight LP half-integrality as a useful tool. They also identify an open question about edge-deletion Node Multicut.
5 Conclusions
- Node Multiway Cut is fixed-parameter tractable above both the largest isolating cut and the optimal LP-relaxation cost.The results build on work by Xiao and Guillemot.Source: §5 · p. 8
- The paper argues that half-integral solutions of the natural LP can be more useful than important separators for Node Multiway Cut.It poses using linear programming in other graph separation problems, such as Directed Feedback Vertex Set, as a question.Source: §5 · p. 8
- Whether the edge-deletion variant of Node Multicut is similarly difficult remains open.The paper has shown that Node Multicut above its LP-relaxation is not in XP.Source: §5 · p. 8