The minimum k-way cut of bounded size is fixed-parameter tractable
From MaRDI portal
Publication:5494963
Abstract: We consider a the minimum k-way cut problem for unweighted graphs with a size bound s on the number of cut edges allowed. Thus we seek to remove as few edges as possible so as to split a graph into k components, or report that this requires cutting more than s edges. We show that this problem is fixed-parameter tractable (FPT) in s. More precisely, for s=O(1), our algorithm runs in quadratic time while we have a different linear time algorithm for planar graphs and bounded genus graphs. Our tractability result stands in contrast to known W[1] hardness of related problems. Without the size bound, Downey et al.[2003] proved that the minimum k-way cut problem is W[1] hard in k even for simple unweighted graphs. Downey et al. asked about the status for planar graphs. Our result implies tractability in k for the planar graphs since the minimum k-way cut of a planar graph is of size at most 6k (more generally, we get tractability in k for any graph class with k-way cuts of size limited by is a function of k, e.g., bounded degree graphs, or simple graphs with an excluded minor). A simple reduction shows that vertex cuts are at least as hard as edge cuts, so the minimum k-way vertex cut is also W[1] hard in terms of k. Marx [2004] proved that finding a minimum k-way vertex cut of size s is also W[1] hard in s. Marx asked about the FPT status with edge cuts, which we prove tractable here. We are not aware of any other cut problem where the vertex version is W[1] hard but the edge version is FPT.
Recommendations
- Cutting up is hard to do: the parameterised complexity of \(k\)-cut and related problems
- Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset
- Complexity and approximability of the \(k\)-way vertex cut
- Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset
- Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
Cited in
(32)- Balanced judicious bipartition is fixed-parameter tractable
- Designing FPT algorithms for cut problems using randomized contractions
- On the complexity of computing the \(k\)-restricted edge-connectivity of a graph
- Partitioning subclasses of chordal graphs with few deletions
- On the Parameterized Complexity of Counting Small-Sized Minimum \(\boldsymbol{(S,T)}\)-Cuts
- Balanced Judicious Bipartition is Fixed-Parameter Tractable
- A tight lower bound for planar multiway cut with fixed number of terminals
- Parameterized complexity dichotomy for \textsc{Steiner Multicut}
- Partitioning subclasses of chordal graphs with few deletions
- Parametrized complexity of length-bounded cuts and multi-cuts
- Euler digraphs
- Linear kernels for separating a graph into components of bounded size
- A survey of parameterized algorithms and the complexity of edge modification
- Fixed-parameter tractability for minimum tree cut/paste distance and minimum common integer partition
- On Weighted Graph Separation Problems and Flow Augmentation
- Reducing CMSO model checking to highly connected graphs
- Complexity and approximability of the \(k\)-way vertex cut
- Parameterized algorithms for min-max multiway cut and list digraph homomorphism
- Covering Vectors by Spaces: Regular Matroids
- Fast and Deterministic Approximations for k-Cut.
- A parameterized approximation scheme for min \(k\)-cut
- Single-exponential FPT algorithms for enumerating secluded \(\mathcal{F}\)-free subgraphs and deleting to scattered graph classes
- Brief announcement: Bounded-degree cut is fixed-parameter tractable
- On the complexity of computing the \(k\)-restricted edge-connectivity of a graph
- Minimum violation vertex maps and their applications to cut problems
- An O^(1.84ᵏ) parameterized algorithm for the multiterminal cut problem
- Editing to Connected F-Degree Graph
- Computation and algorithm for the minimum \(k\)-edge-connectivity of graphs
- Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time
- Minimum Bisection Is Fixed-Parameter Tractable
- Clique Cover and Graph Separation
- Fast and deterministic approximations for \(k\)-cut
This page was built for publication: The minimum \(k\)-way cut of bounded size is fixed-parameter tractable
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5494963)
