The Minimum k-way Cut of Bounded Size is Fixed-Parameter Tractable

DOI10.1109/FOCS.2011.53zbMath1292.68094arXiv1101.4689MaRDI QIDQ5494963

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)

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

Mathematics Subject Classification ID

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

Related Items (25)

Linear kernels for separating a graph into components of bounded size ⋮ Parameterized complexity dichotomy for \textsc{Steiner Multicut} ⋮ Designing FPT Algorithms for Cut Problems Using Randomized Contractions ⋮ Covering Vectors by Spaces: Regular Matroids ⋮ Parameterized algorithms for min-max multiway cut and list digraph homomorphism ⋮ Clique Cover and Graph Separation ⋮ Partitioning subclasses of chordal graphs with few deletions ⋮ Partitioning subclasses of chordal graphs with few deletions ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Unnamed Item ⋮ On Weighted Graph Separation Problems and Flow Augmentation ⋮ An \(O^\ast(1.84^k)\) parameterized algorithm for the multiterminal cut problem ⋮ Minimum Violation Vertex Maps and Their Applications to Cut Problems ⋮ Balanced Judicious Bipartition is Fixed-Parameter Tractable ⋮ Minimum Bisection Is Fixed-Parameter Tractable ⋮ Reducing CMSO model checking to highly connected graphs ⋮ Fast and Deterministic Approximations for k-Cut. ⋮ On the complexity of computing the \(k\)-restricted edge-connectivity of a graph ⋮ Unnamed Item ⋮ On the Complexity of Computing the k-restricted Edge-connectivity of a Graph ⋮ Editing to Connected F-Degree Graph ⋮ Balanced Judicious Bipartition is Fixed-Parameter Tractable ⋮ Computation and algorithm for the minimum \(k\)-edge-connectivity of graphs ⋮ Euler Digraphs ⋮ Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time

This page was built for publication: The Minimum k-way Cut of Bounded Size is Fixed-Parameter Tractable