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

DOI10.1137/1.9781611974331.CH81zbMATH Open1410.68307MaRDI QIDQ6829520FDOQ6829520

Authors: Marcin Pilipczuk, Magnus Wahlström 

Publication date: 16 July 2018

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

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) 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)

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

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