Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset

DOI10.1137/110855247zbMath1304.68078arXiv1010.3633OpenAlexW1978447499MaRDI QIDQ5494921

Dániel Marx, Igor Razgon

Publication date: 30 July 2014

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

parameterized complexitymulticutgraph separation problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (32)

Linear kernels for separating a graph into components of bounded size ⋮ Adapting the directed grid theorem into an \textsf{FPT} algorithm ⋮ Parameterized complexity dichotomy for \textsc{Steiner Multicut} ⋮ Linear Time Parameterized Algorithms for Subset Feedback Vertex Set ⋮ Finding all leftmost separators of size \(\le k\) ⋮ 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 ⋮ Colourful components in \(k\)-caterpillars and planar graphs ⋮ Adapting the Directed Grid Theorem into an FPT Algorithm ⋮ Hitting Selected (Odd) Cycles ⋮ Parameterized complexity of weighted multicut in trees ⋮ Parameterized complexity of multicut in weighted trees ⋮ Fission: Practical algorithms for computing minimum balanced node separators ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Unnamed Item ⋮ On Weighted Graph Separation Problems and Flow Augmentation ⋮ Multicut Is FPT ⋮ Balanced Judicious Bipartition is Fixed-Parameter Tractable ⋮ Minimum Bisection Is Fixed-Parameter Tractable ⋮ Odd Multiway Cut in Directed Acyclic Graphs ⋮ A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs With a Fixed Number of Terminals ⋮ Multi-Budgeted Directed Cuts ⋮ Parameterized complexity of critical node cuts ⋮ An FPT algorithm for planar multicuts with sources and sinks on the outer face ⋮ List H-coloring a graph by removing few vertices ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Faster graph bipartization ⋮ Quick separation in chordal and split graphs ⋮ Balanced Judicious Bipartition is Fixed-Parameter Tractable ⋮ Multi-budgeted directed cuts

This page was built for publication: Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset