Source-linked AI summary
Fixed-parameter tractability of multicut parameterized by the size of the cutset
Dániel Marx, Igor Razgon
TL;DR
The paper asks whether undirected Vertex Multicut and Edge Multicut are fixed-parameter tractable when parameterized only by cutset size. It develops compression-based structural and sampling techniques, proving an O∗(2^O(p^3)) algorithm and showing that Directed Multicut is W[1]-hard under the same parameterization.
Problem
The central question is whether undirected Vertex Multicut and Edge Multicut admit fixed-parameter algorithms parameterized by solution size p.
Method
The approach combines iterative compression, a reduction to Almost 2SAT under special structural properties, and random sampling of vertex subsets with torso contractions.
Results
O∗(2^O(p^3)) time suffices to find a size-p solution for undirected Vertex Multicut or Edge Multicut, while Directed Multicut is W[1]-hard parameterized by p.
Takeaways & Limitations
The results establish fixed-parameter tractability for both undirected multicut variants and settle the cited open parameterized-complexity question.
Takeaways & Limitations
The paper leaves the complexity of Directed Multicut for k=3, and of the problem parameterized jointly by k and p, open.
Abstract
from arXiv · showhide
Given an undirected graph $G$, a collection $\{(s_1,t_1),..., (s_k,t_k)\}$ of pairs of vertices, and an integer $p$, the Edge Multicut problem ask if there is a set $S$ of at most $p$ edges such that the removal of $S$ disconnects every $s_i$ from the corresponding $t_i$. Vertex Multicut is the analogous problem where $S$ is a set of at most $p$ vertices. Our main result is that both problems can be solved in time $2^{O(p^3)}... n^{O(1)}$, i.e., fixed-parameter tractable parameterized by the size $p$ of the cutset in the solution. By contrast, it is unlikely that an algorithm with running time of the form $f(p)... n^{O(1)}$ exists for the directed version of the problem, as we show it to be W[1]-hard parameterized by the size of the cutset.
1 Introduction
The paper establishes fixed-parameter tractability for undirected Vertex Multicut and Edge Multicut parameterized by solution size, using compression, structural reductions, and random sampling. It also shows directed multicut is W[1]-hard under the same parameterization.
- Problem setting: Edge Multicut generalizes minimum s−t cut by requiring selected edges to separate multiple terminal pairs, while Vertex Multicut removes vertices instead.Edge Multicut is polynomial-time solvable for k≤2 but NP-hard for every fixed k≥3.
- Main result: Theorem 1.1 gives an O∗(2^O(p^3)) algorithm for finding a size-p solution for either undirected multicut variant, if one exists.The O∗ notation suppresses factors polynomial in the input size.
- Main result: The result proves both undirected variants are fixed-parameter tractable when parameterized by the size p of the cutset.It also implies polynomial-time solvability when the optimum solution size is O(∛log n).
- Techniques: The algorithm begins with iterative compression, reduces the compression problem to Almost 2SAT, and relies on two structural properties of the instance.The properties require components outside W to have at most two legs and ensure no vertex lies in the shadow of the solution.
- Techniques: Random sampling and torso contractions remove parts unreachable from W with positive probability while preserving the solution.The paper describes this sampling as the mechanism for achieving the shadow-related structural property.
- Directed graphs: For directed graphs, the paper proves Directed Multicut is W[1]-hard parameterized by solution size p.This contrasts with the fixed-parameter tractability result for undirected graphs.
2 Framework: compression, shadows, legs
The framework reduces Multicut Compression through shadowless and bipedal instances, then solves the structured problem using a bounded-size algorithm. These reductions yield an FPT algorithm with running time O∗(2O(p^3)).
- Compression: The compression formulation receives a multicut W and seeks a size-at-most-p multicut, with additional constraints in its restricted form.The restricted problem requires S to avoid W and separate every pair of vertices in W into distinct components.
- Compression: Iterative compression or approximation reduces the original problem to Multicut Compression instances.Iterative compression uses at most |V(G)| instances with |W| = p + 1; approximation provides an alternative route.
- Shadows: Shadowless reduction produces instances whose solutions preserve feasibility for the original instance and whose shadowless solutions characterize solvability.The reduction creates 2O(p^3) log n instances, and the original instance has a solution if and only if at least one has a shadowless solution.
- Components and legs: Bipedal reduction transforms instances so every component of G \ W has at most two legs while preserving the relevant shadowless solution.A bipedal instance is one in which each component of G \ W is adjacent to at most two vertices of W.
- Algorithm: The bipedal problem can be solved in time O∗(4^p), and combining the reductions proves Multicut Compression∗ is fixed-parameter tractable.The resulting framework processes the reduced instances within O∗(2O((p+log |W|)^3)) time.
3 Making the solution shadowless
The paper reduces Multicut Compression to finding a shadowless solution by using torso operations and randomized sampling of important separators. The sampling covers solution shadows while avoiding the solution itself with probability 2−O(p3), and can be derandomized into a deterministic family.
- Torsos and shadowless solutions: The torso operation preserves separation: a set separates two retained vertices in torso(G, C) exactly when it separates them in G.This safety property underpins the reduction from the original instance to the torso instance.
- Randomized reduction: The reduction seeks a set Z that covers a hypothetical solution’s shadow while remaining disjoint from the solution.Torsoing away Z then makes the solution shadowless without creating new solutions.
- Random sampling: RandomSet produces Z such that, for every W-closest set R with |N(R)| ≤p, Z avoids N(R) and covers V(G) \ (R ∪N(R)) with probability at least 2−O(p3).These events ensure that the relevant solution becomes shadowless after the torso operation.
- Important separators: The sampling method enumerates at most 4p important X−Y separators of size at most p and uses them to characterize closest-set boundaries.For each vertex outside a closest set, an important separator contained in the boundary is available.
- Shadow bounds: Each vertex belongs to the exact shadow of at most 4p members of Ip, while clique-induced separators reduce this bound to p.These bounds control the probability analysis of the randomized selection process.
- Derandomization: The randomized transformation succeeds with probability 2−O(p3), and derandomization produces 2O(p3) log^2 |V(G)| candidate sets.The resulting deterministic construction uses 2O(p3) ·log^2 n sets and supports the algorithm’s branching procedure.
4 Reduction to the bipedal case
The reduction transforms Multicut Compression instances into bounded-leg instances through branching on components with more than two legs. Shattering sets control this branching, yielding a bounded search tree and either a direct bipedal instance or equivalent recursive subinstances.
- A solution of Multicut Compression must separate W and therefore the number of non-trivial components lower-bounds the solution size.
- The branching rule either deletes a vertex in B and decreases p by one, or contracts vertices according to a function f assigning them to legs of the component.The resulting instances preserve the implication from a solution of a branch to a solution of the original instance.
- Shattering sets ensure that every branch either rules out a separator configuration or increases the number of non-trivial components.
- A shattering set B of size at most 3p can be found in polynomial time for every component with more than two legs.
- The recursion uses measure 2p − κ, has height at most 2p, and branches at most 3^p + |W|^3p ways at each step.When terminal cases apply, the algorithm solves the multiway cut instance, rejects impossible zero-parameter cases, or returns a bipedal instance.
- A good multiway cut either yields a shattering set of size at most 3p or can be replaced by a smaller good multiway cut.This provides the key polynomial-time procedure for obtaining the branching structure.
5 Finding a shadowless solution by reduction to Almost 2SAT
The bipedal compression problem is encoded as Almost 2SAT by assigning each nonterminal vertex a Boolean side relative to its component’s legs. Deleting at most p variables then corresponds to finding a shadowless multicut solution.
- The goal is to solve Bipedal Multicut Compression when a shadowless solution is guaranteed to exist.
- Almost 2SAT asks for deletion of at most k variables so that a 2CNF formula becomes satisfiable, and is solvable in O*(2.3146^k) time.
- Each vertex outside W receives a variable whose value records which leg of its component remains reachable from that vertex.The shadowless assumption excludes vertices separated from both legs.
- The formula enforces adjacency consistency, fixed values for vertices adjacent to legs, separation of terminal pairs, and separation from terminals in W.
- A shadowless multicut solution induces a satisfying assignment after deleting the variables corresponding to its cut vertices.
- The constructed cut is verified to be a multiway cut of W and to separate every terminal pair.
6 Hardness of Directed Multicut
Directed Multicut is shown W[1]-hard parameterized by the cutset size through a reduction from Clique. Gadgets encode ordered adjacent vertex pairs, while connections enforce consistency between their choices.
- Directed Edge Multicut is W[1]-hard parameterized by the size p of the cutset.
- The reduction constructs t(t −1) gadgets, one for each ordered pair of clique positions, with states representing ordered pairs of adjacent vertices.
- The construction also enforces consistency among gadgets sharing a clique position, and a clique yields a multicut within the stated budget.
- Each gadget contains n^2 possible states, and finite-weight edges correspond exactly to adjacent vertex pairs in the source graph.
- The budget p forces exactly one weight-D edge to be selected from each gadget, thereby choosing one represented pair per gadget.
- Connections between G_i,j and G_j,i enforce that the two gadgets represent reversed ordered pairs.
A Important separators
The appendix bounds the number of important separators using submodularity and recursive branching. It establishes a compact family of separators that can be enumerated efficiently.
- Important X−Y separators are analyzed using the reachable-side set K_S and the boundary function γ(Z)=|N(Z)|.
- Removing a vertex from an important separator preserves importance in the graph with that vertex deleted, while enlarging X preserves importance when the separator remains valid.
- There are at most 2^(2p−λ) important X−Y separators of size at most p, where λ is the minimum separator size.
- Submodularity implies a unique minimum X−Y separator whose reachable side is inclusionwise maximal.
- Every important separator’s reachable side contains the reachable side of that canonical minimum separator.
- A maximum-flow computation identifies a canonical separator, after which branching enumerates all important separators within the bound.
B Deleting variables in Almost 2SAT
The reduction replaces each variable of φ with two variables in φ′, encoding truth assignments while adding clauses that enforce consistency. It establishes an equal-size correspondence between deleting variables from φ and deleting clauses from φ′, enabling an O*(4^k) algorithm.
- Reduction: The construction creates a 2CNF formula φ′ with 2n variables, x_i^0 and x_i^1, for the n variables of φ.The intended encoding represents whether the original variable x_i takes each Boolean value.
- Reduction: Each original clause is copied into φ′ by replacing positive and negative literals with the corresponding encoded variables.Positive and negative occurrences are mapped to x_i^1 and x_i^0, respectively.
- Correctness: There is a set X of variables with φ \ X satisfiable if and only if an equal-size clause set X′ makes φ′ \ X′ satisfiable.A satisfying assignment is translated in both directions between the original and transformed formulas.
- Algorithmic consequence: The existence of X′ can be tested in O*(4^k) time, yielding the theorem’s algorithm.The runtime follows by applying the cited algorithm to the transformed formula after the equivalence is established.
- Correctness: Any deleted clause set X′ can be assumed to contain only consistency clauses of the form (x_i^0).If a deleted clause contains x_i^b positively, it can be replaced by the corresponding consistency clause while adjusting the assignment.