Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs

DOI10.1007/978-3-642-31594-7_49zbMath1272.68158arXiv1202.5749OpenAlexW2065803871MaRDI QIDQ5891121

Magnus Wahlström, Stefan Kratsch, Michał Pilipczuk, Marcin Pilipczuk

Publication date: 12 August 2013

Published in: SIAM Journal on Discrete Mathematics, Automata, Languages, and Programming (Search for Journal in Brave)

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

zbMATH Keywords

directed acyclic graphfixed-parameter tractabilitymulticutshadow removalimportant separators

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40)

Related Items (25)

Adapting the directed grid theorem into an \textsf{FPT} algorithm ⋮ Parameterized complexity dichotomy for \textsc{Steiner Multicut} ⋮ Odd Multiway Cut in Directed Acyclic Graphs ⋮ What’s Next? Future Directions in Parameterized Complexity ⋮ Designing FPT Algorithms for Cut Problems Using Randomized Contractions ⋮ Clique Cover and Graph Separation ⋮ The complexity of multicut and mixed multicut problems in (di)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 ⋮ On the Parameterized Complexity of Counting Small-Sized Minimum \(\boldsymbol{(S,T)}\)-Cuts ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ On Weighted Graph Separation Problems and Flow Augmentation ⋮ Multicut Is FPT ⋮ Parameterized complexity of critical node cuts ⋮ List H-coloring a graph by removing few vertices ⋮ Unnamed Item ⋮ NP-Hardness and Fixed-Parameter Tractability of Realizing Degree Sequences with Directed Acyclic Graphs ⋮ Feedback edge sets in temporal graphs ⋮ On the parameterized complexity of deletion to \(\mathcal{H}\)-free strong components ⋮ A relaxation of the directed disjoint paths problem: a global congestion metric helps ⋮ A Relaxation of the Directed Disjoint Paths Problem: A Global Congestion Metric Helps. ⋮ Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset ⋮ Acyclic Digraphs

This page was built for publication: Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs