Directed multicut is W[1]-hard, even for four terminal pairs
From MaRDI portal
Publication:4575662
DOI10.1137/1.9781611974331.ch81zbMath1410.68307arXiv1507.02178MaRDI 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
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85: Graph algorithms (graph-theoretic aspects)