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
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
This page was built for publication: Directed multicut is W[1]-hard, even for four terminal pairs