The minimum k-way cut of bounded size is fixed-parameter tractable

DOI10.1109/FOCS.2011.53zbMATH Open1292.68094arXiv1101.4689MaRDI QIDQ5494963FDOQ5494963

Authors: Ken-ichi Kawarabayashi, Mikkel Thorup 

Publication date: 30 July 2014

Published in: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1101.4689

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

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Connectivity (05C40) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cited In (32)

• Balanced judicious bipartition is fixed-parameter tractable
• Partitioning subclasses of chordal graphs with few deletions
• Designing FPT algorithms for cut problems using randomized contractions
• On the complexity of computing the \(k\)-restricted edge-connectivity of a graph
• 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
• A survey of parameterized algorithms and the complexity of edge modification
• Linear kernels for separating a graph into components of bounded size
• Fixed-parameter tractability for minimum tree cut/paste distance and minimum common integer partition
• On Weighted Graph Separation Problems and Flow Augmentation
• Title not available (Why is that?)
• 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
• Fast and Deterministic Approximations for k-Cut.
• Covering Vectors by Spaces: Regular Matroids
• 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
• Minimum violation vertex maps and their applications to cut problems
• On the complexity of computing the \(k\)-restricted edge-connectivity of a graph
• Editing to Connected F-Degree Graph
• An \(O^\ast(1.84^k)\) parameterized algorithm for the multiterminal cut problem
• 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

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)