Marcin Pilipczuk
Skip Abstract Section
Abstract
We prove that Multicut in directed graphs, parameterized by the size of the cutset, is W[1]-hard and hence unlikely to be fixed-parameter tractable even if restricted to instances with only four terminal pairs. This negative result almost completely resolves one of the central open problems in the area of parameterized complexity of graph separation problems, posted originally by Marx and Razgon [SIAM J. Comput. 43(2):355--388 (2014)], leaving only the case of three terminal pairs open. The case of two terminal pairs was shown to be FPT by Chitnis et al. [SIAM J. Comput. 42(4):1674--1696 (2013)].
Our gadget methodology also allows us to prove W[1]-hardness of the Steiner Orientation problem parameterized by the number of terminal pairs, resolving an open problem of Cygan, Kortsarz, and Nutov [SIAM J. Discrete Math. 27(3):1503-1513 (2013)].
- Saeed Akhoondian Amiri, Lukasz Kaiser, Stephan Kreutzer, Roman Rabinovich, and Sebastian Siebertz. 2015. Graph searching games and width measures for directed graphs. In Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science (STACS’15) (LIPIcs’15), Vol. 30, Ernst W. Mayr and Nicolas Ollinger (Eds.). Schloss Dagstuhl—Leibniz-Zentrum fuer Informatik, 34--47.Google Scholar
- Joergen Bang-Jensen and Gregory Gutin. 2008. Digraphs: Theory, Algorithms and Applications. Springer. Google ScholarDigital Library
- Nicolas Bousquet, Jean Daligault, and Stéphan Thomassé. 2011. Multicut is FPT. In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, 6-8 June 2011, Lance Fortnow and Salil P. Vadhan (Eds.). ACM, 459--468. Google ScholarDigital Library
- Jianer Chen, Yang Liu, and Songjian Lu. 2009. An improved parameterized algorithm for the minimum node multiway cut problem. Algorithmica 55, 1 (2009), 1--13. Google ScholarDigital Library
- Jianer Chen, Yang Liu, Songjian Lu, Barry O’Sullivan, and Igor Razgon. 2008. A fixed-parameter algorithm for the directed feedback vertex set problem. J. ACM 55, 5 (2008). Google ScholarDigital Library
- Rajesh Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, Marcin Pilipczuk, and Michal Pilipczuk. 2016. Designing FPT algorithms for cut problems using randomized contractions. SIAM J. Comput. 45, 4 (2016), 1171--1229.Google ScholarDigital Library
- Rajesh Chitnis, László Egri, and Dániel Marx. 2017. List H-coloring a graph by removing few vertices. Algorithmica 78, 1 (2017), 110--146. Google ScholarDigital Library
- Rajesh Hemant Chitnis, MohammadTaghi Hajiaghayi, and Dániel Marx. 2013. Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset. SIAM J. Comput. 42, 4 (2013), 1674--1696.Google ScholarCross Ref
- Marek Cygan, Guy Kortsarz, and Zeev Nutov. 2013. Steiner forest orientation problems. SIAM J. Discrete Math. 27, 3 (2013), 1503--1513.Google ScholarCross Ref
- Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, and Magnus Wahlström. 2014. Clique cover and graph separation: New incompressibility results. TOCT 6, 2 (2014), 6. Google ScholarDigital Library
- Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. 2014. Minimum bisection is fixed parameter tractable. In Proceedings of the Symposium on Theory of Computing (STOC’14), David B. Shmoys (Ed.). ACM, 323--332. Google ScholarDigital Library
- Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, and Jakub Onufry Wojtaszczyk. 2013. On multiway cut parameterized above lower bounds. TOCT 5, 1 (2013), 3. Google ScholarDigital Library
- P. Erdős and R. Rado. 1960. Intersection theorems for systems of sets. J. London Math. Soc. s1-35, 1 (1960), 85--90. arXiv:http://jlms.oxfordjournals.org/content/s1-35/1/85.full.pdf+htmlGoogle Scholar
- Jörg Flum and Martin Grohe. 2006. Parameterized Complexity Theory. Springer. Google ScholarDigital Library
- Robert Ganian, Petr Hlinený, Joachim Kneis, Alexander Langer, Jan Obdrzálek, and Peter Rossmanith. 2014. Digraph width measures in parameterized algorithmics. Discrete Appl. Math. 168, 0 (2014), 88--107. Google ScholarDigital Library
- Robert Ganian, Petr Hlinený, Joachim Kneis, Daniel Meister, Jan Obdrzálek, Peter Rossmanith, and Somnath Sikdar. 2016. Are there any good digraph width measures? J. Comb. Theory, Ser. B 116 (2016), 250--286. Google ScholarDigital Library
- Danny Hermelin, Stefan Kratsch, Karolina Soltys, Magnus Wahlström, and Xi Wu. 2015. A completeness theory for polynomial (turing) kernelization. Algorithmica 71, 3 (2015), 702--730. Google ScholarDigital Library
- Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. 2001. Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63, 4 (2001), 512--530. Google ScholarDigital Library
- Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, and Magnus Wahlström. 2015. Fixed-parameter tractability of multicut in directed acyclic graphs. SIAM J. Discrete Math. 29, 1 (2015), 122--144.Google ScholarCross Ref
- Stephan Kreutzer and Sebastian Ordyniak. 2014. Width-measures for directed graphs and algorithmic applications. In Quantitative Graph Theory: Mathematical Foundations and Applications, Matthias Dehmer and Frank Emmert-Streib (Eds.). Chapman and Hall/CRC Press.Google Scholar
- Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. 2011. Lower bounds based on the exponential time hypothesis. Bull. EATCS 105 (2011), 41--72. http://albcom.lsi.upc.edu/ojs/index.php/beatcs/article/view/96.Google Scholar
- Daniel Lokshtanov, N. S. Narayanaswamy, Venkatesh Raman, M. S. Ramanujan, and Saket Saurabh. 2014. Faster parameterized algorithms using linear programming. ACM Trans. Algorithms 11, 2 (2014), 15:1--15:31. Google ScholarDigital Library
- Dániel Marx. 2006. Parameterized graph separation problems. Theor. Comput. Sci. 351, 3 (2006), 394--406. Google ScholarDigital Library
- Dániel Marx. 2010. Can you beat treewidth? Theor. Comput. 6, 1 (2010), 85--112.Google ScholarCross Ref
- Dániel Marx. 2011. Important separators and parameterized algorithms. Lecture slides retrieved from http://www.cs.bme.hu/dmarx/papers/marx-mds-separators-slides.pdf.Google Scholar
- Dániel Marx. 2012. What’s next? Future directions in parameterized complexity. In The Multivariate Algorithmic Revolution and Beyond—Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday, Lecture Notes in Computer Science, Vol. 7370, Hans L. Bodlaender, Rod Downey, Fedor V. Fomin, and Dániel Marx (Eds.). Springer, 469--496. Google ScholarDigital Library
- Dániel Marx, Barry O’Sullivan, and Igor Razgon. 2013. Finding small separators in linear time via treewidth reduction. ACM Trans. Algorithms 9, 4 (2013), 30. Google ScholarDigital Library
- Dániel Marx and Igor Razgon. 2014. Fixed-parameter tractability of multicut parameterized by the size of the cutset. SIAM J. Comput. 43, 2 (2014), 355--388.Google ScholarCross Ref
- Marcin Pilipczuk and Magnus Wahlström. 2016. Directed multicut is W{1}-hard, even for four terminal pairs. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, January 10-12, 2016, Robert Krauthgamer (Ed.). SIAM, 1167--1178. Google ScholarDigital Library
- Igor Razgon and Barry O’Sullivan. 2009. Almost 2-SAT is fixed-parameter tractable. J. Comput. Syst. Sci. 75, 8 (2009), 435--450. Google ScholarDigital Library
- Magnus Wahlström. 2014. Half-integrality, LP-branching and FPT algorithms. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, January 5-7, 2014, Chandra Chekuri (Ed.). SIAM, 1762--1781. Google ScholarDigital Library
Index Terms
- Directed Multicut is W[1]-hard, Even for Four Terminal Pairs
Recommendations
Directed multicut is W[1]-hard, even for four terminal pairs
SODA '16: Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithmsWe prove that MULTICUT in directed graphs, parameterized by the size of the cutset, is W[1]-hard and hence unlikely to be fixed-parameter tractable even if restricted to instances with only four terminal pairs. This negative result almost completely ...
Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs
The Multicut problem, given a graph G, a set of terminal pairs $\mathcal{T}=\{(s_i,t_i)\ |\ 1\leq i\leq r\}$, and an integer $p$, asks whether one can find a cutset consisting of at most $p$ nonterminal vertices that separates all the terminal pairs, i.e., ...
An algorithmic metatheorem for directed treewidth
The notion of directed treewidth was introduced by Johnson et al. (2001) as a first step towards an algorithmic metatheory for digraphs. They showed that some NP-complete properties such as Hamiltonicity can be decided in polynomial time on digraphs of ...
Comments