Parameterized complexity dichotomy for Steiner Multicut

DOI10.4230/LIPICS.STACS.2015.157MaRDI QIDQ2954992zbMATH OpenFDO

Authors Karl Bringmann, Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen

Publication date 24 January 2017

zbMATH Keywords

fixed-parameter tractabilitygraph cut problemsSteiner cut

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Connectivity (05C40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Parameterized complexity dichotomy for \textsc{Steiner Multicut}
• Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
• Fixed-parameter tractability of multicut parameterized by the size of the cutset
• Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth
• SOFSEM 2006: Theory and Practice of Computer Science

Cited in

(5)

• Designing FPT algorithms for cut problems using randomized contractions
• Parameterized complexity dichotomy for \textsc{Steiner Multicut}
• On structural parameterizations of Hitting Set: hitting paths in graphs using 2-SAT
• Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters
• On structural parameterizations of \textsc{Hitting Set}: hitting paths in graphs using 2-SAT

This page was built for publication: Parameterized complexity dichotomy for Steiner Multicut

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2954992)