Directed multicut is W[1]-hard, even for four terminal pairs

DOI10.1137/1.9781611974331.ch81zbMath1410.68307arXiv1507.02178OpenAlexW2239537367MaRDI QIDQ4575662

Marcin Pilipczuk, Magnus Wahlström

Publication date: 16 July 2018

Published in: ACM Transactions on Computation Theory, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

fixed-parameter tractabilitydirected treewidthdirected multicutSteiner orientation

Mathematics Subject Classification ID

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

Related Items

Adapting the directed grid theorem into an \textsf{FPT} algorithm ⋮ Exact and approximation algorithms for sensor placement against DDoS attacks ⋮ Designing FPT Algorithms for Cut Problems Using Randomized Contractions ⋮ Adapting the Directed Grid Theorem into an FPT Algorithm ⋮ Parameterized complexity of multicut in weighted trees ⋮ On the fixed-parameter tractability of the maximum connectivity improvement problem ⋮ 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 ⋮ Multi-Budgeted Directed Cuts ⋮ A tight lower bound for planar Steiner orientation ⋮ Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions) ⋮ On the parameterized complexity of separating certain sources from the target ⋮ Multi-budgeted directed cuts ⋮ Acyclic Digraphs

This page was built for publication: Directed multicut is W[1]-hard, even for four terminal pairs