Multicut is FPT

DOI10.1145/1993636.1993698zbMath1288.05264OpenAlexW2082223143MaRDI QIDQ5419116

Jean Daligault, Nicolas Bousquet, Steéphan Thomassé

Publication date: 5 June 2014

Published in: Proceedings of the forty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1993636.1993698

zbMATH Keywords

parameterized complexityFPTmulticut

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (29)

Linear kernels for separating a graph into components of bounded size ⋮ On Multiway Cut Parameterized above Lower Bounds ⋮ On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal ⋮ Parameterized complexity dichotomy for \textsc{Steiner Multicut} ⋮ What’s Next? Future Directions in Parameterized Complexity ⋮ Designing FPT Algorithms for Cut Problems Using Randomized Contractions ⋮ Cluster Editing ⋮ Multicuts in planar and bounded-genus graphs with bounded number of terminals ⋮ Clique Cover and Graph Separation ⋮ The complexity of multicut and mixed multicut problems in (di)graphs ⋮ Hitting Selected (Odd) Cycles ⋮ Improved parameterized and exact algorithms for cut problems on trees ⋮ Multicut Is FPT ⋮ On the generalized multiway cut in trees problem ⋮ Multicut in trees viewed through the eyes of vertex cover ⋮ Restricted vertex multicut on permutation graphs ⋮ An \(O^\ast(1.84^k)\) parameterized algorithm for the multiterminal cut problem ⋮ Confronting intractability via parameters ⋮ On the parameterized complexity of finding separators with non-hereditary properties ⋮ A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs With a Fixed Number of Terminals ⋮ Subset Feedback Vertex Set Is Fixed-Parameter Tractable ⋮ Parameterized complexity of critical node cuts ⋮ An FPT algorithm for planar multicuts with sources and sinks on the outer face ⋮ Fixed-Parameter Algorithms for Finding Agreement Supertrees ⋮ Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth ⋮ Important Separators and Parameterized Algorithms ⋮ On the parameterized complexity of separating certain sources from the target ⋮ Unnamed Item ⋮ Unnamed Item

This page was built for publication: Multicut is FPT