Document Open Access Logo

Parameterized Complexity Dichotomy for Steiner Multicut

Authors Karl Bringmann, Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen

PDF
Thumbnail PDF

File

LIPIcs.STACS.2015.157.pdf
  • Filesize: 0.71 MB
  • 14 pages

Document Identifiers

Author Details

Karl Bringmann
Danny Hermelin
Matthias Mnich
Erik Jan van Leeuwen

Cite As Get BibTex

Karl Bringmann, Danny Hermelin, Matthias Mnich, and Erik Jan van Leeuwen. Parameterized Complexity Dichotomy for Steiner Multicut. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 157-170, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.STACS.2015.157

Abstract

We consider the Steiner Multicut problem, which asks, given an undirected graph G, a collection T = \{T_{1},...,T_{t}}, T_i \subseteq V(G), of terminal sets of size at most p, and an integer k, whether there is a set S of at most k edges or nodes such that of each set T_{i} at least one pair of terminals is in different connected components of G \ S. This problem generalizes several well-studied graph cut problems, in particular the Multicut problem, which corresponds to the case p = 2. The Multicut problem was recently shown to be fixed-parameter tractable for parameter k [Marx and Razgon, Bousquet et al., STOC 2011]. The question whether this result generalizes to Steiner Multicut motivates the present work.

We answer the question that motivated this work, and in fact provide a dichotomy of the parameterized complexity of Steiner Multicut on general graphs. That is, for any combination of k, t, p, and the treewidth tw(G) as constant, parameter, or unbounded, and for all versions of the problem (edge deletion and node deletion with and without deletable terminals), we prove either that the problem is fixed-parameter tractable or that the problem is hard (W[1]-hard or even (para-)NP-complete). Among the many results in the paper, we highlight that:

- The edge deletion version of Steiner Multicut is fixed-parameter tractable for parameter k+t on general graphs (but has no polynomial kernel, even on trees).
- In contrast, both node deletion versions of Steiner Multicut are W[1]-hard for the parameter k+t on general graphs.
- All versions of Steiner Multicut are W[1]-hard for the parameter k, even when p=3 and the graph is a tree plus one node. 
  
Since we allow k, t, p, and tw(G) to be any constants, our characterization includes a dichotomy for Steiner Multicut on trees (for tw(G) = 1) as well as a polynomial time versus NP-hardness dichotomy (by restricting k,t,p,tw(G) to constant or unbounded).

Subject Classification

Keywords
  • graph cut problems
  • Steiner cut
  • fixed-parameter tractability

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Ajit Agrawal, Philip Klein, and R. Ravi. When trees collide: an approximation algorithm for the generalized Steiner problem on networks. SIAM J. Comput., 24(3):440-456, 1995. Google Scholar
  2. Adi Avidor and Michael Langberg. The multi-multiway cut problem. Theoret. Comput. Sci., 377(1-3):35-42, 2007. Google Scholar
  3. Nicolas Bousquet, Jean Daligault, and Stéphan Thomassé. Multicut is FPT. In Proc. STOC 2011, pages 459-468, New York, NY, USA, 2011. ACM. Google Scholar
  4. Gruia Călinescu, Cristina G. Fernandes, and Bruce Reed. Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width. J. Algorithms, 48(2):333-359, 2003. Google Scholar
  5. Yixin Cao, Jianer Chen, and Jia-Hao Fan. An O^*(1.84^k) parameterized algorithm for the multiterminal cut problem. Information Processing Letters, 114(4):167-173, 2014. Google Scholar
  6. Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, and D. Sivakumar. On the hardness of approximating multicut and sparsest-cut. Comput. Complexity, 15(2):94-114, 2006. Google Scholar
  7. Jianer Chen, Yang Liu, and Songjian Lu. An improved parameterized algorithm for the minimum node multiway cut problem. Algorithmica, 55(1):1-13, 2009. Google Scholar
  8. Rajesh Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, Marcin Pilipczuk, and Michal Pilipczuk. Designing FPT algorithms for cut problems using randomized contractions. In Proc. FOCS 2012, pages 460-469, Washington, DC, USA, 2012. IEEE Computer Society. Google Scholar
  9. Marek Cygan, Łukasz Kowalik, and Marcin Pilipczuk. Open problems from workshop on kernels, April 2013. URL: http://worker2013.mimuw.edu.pl/slides/worker-opl.pdf.
  10. Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk, and Magnus Wahlström. Clique cover and graph separation: new incompressibility results. ACM Transactions on Computation Theory (TOCT), 6(2), 2014. Google Scholar
  11. Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, and Jakub Onufry Wojtaszczyk. On multiway cut parameterized above lower bounds. ACM Transactions on Computation Theory (TOCT), 5(1), 2013. Google Scholar
  12. E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. D. Seymour, and M. Yannakakis. The complexity of multiterminal cuts. SIAM J. Comput., 23(4):864-894, 1994. Google Scholar
  13. G. B. Dantzig and D. R. Fulkerson. On the max-flow min-cut theorem of networks. In Linear inequalities and related systems, Annals of Mathematics Studies, no. 38, pages 215-221. Princeton University Press, Princeton, N. J., 1956. Google Scholar
  14. Michael Dom, Daniel Lokshtanov, and Saket Saurabh. Incompressibility through colors and IDs. In Proc. ICALP 2009, volume 5555 of Lecture Notes Comput. Sci., pages 378-389. Springer, Berlin, 2009. Google Scholar
  15. R. G. Downey and M. R. Fellows. Parameterized complexity. Monographs in Computer Science. Springer-Verlag, New York, 1999. Google Scholar
  16. Rodney G. Downey, Vladimir Estivill-Castro, Michael Fellows, Elena Prieto, and Frances A. Rosamond. Cutting up is hard to do: The parameterised complexity of k-cut and related problems. Electr. Notes Theor. Comput. Sci., 78(0):209 - 222, 2003. Google Scholar
  17. P. Elias, A. Feinstein, and C.E. Shannon. A note on the maximum flow through a network. Information Theory, IRE Transactions on, 2(4):117-119, 1956. Google Scholar
  18. Michael R. Fellows, Danny Hermelin, Frances Rosamond, and Stéphane Vialette. On the parameterized complexity of multiple-interval graph problems. Theoret. Comput. Sci., 410(1):53-61, 2009. Google Scholar
  19. L. R. Ford, Jr. and D. R. Fulkerson. Maximal flow through a network. Canad. J. Math., 8:399-404, 1956. Google Scholar
  20. Naveen Garg, Vijay V. Vazirani, and Mihalis Yannakakis. Approximate max-flow min-(multi)cut theorems and their applications. SIAM J. Comput., 25(2):235-251, 1996. Google Scholar
  21. Sylvain Guillemot. FPT algorithms for path-transversal and cycle-transversal problems. Discrete Optim., 8(1):61-71, 2011. Google Scholar
  22. Jiong Guo, Falk Hüffner, Erhan Kenar, Rolf Niedermeier, and Johannes Uhlmann. Complexity and exact algorithms for multicut. In Proc. SOFSEM 2006, volume 3831 of Lecture Notes Comput. Sci., pages 303-312, Berlin, 2006. Springer. Google Scholar
  23. Jiong Guo and Rolf Niedermeier. Fixed-parameter tractability and data reduction for multicut in trees. Networks, 46(3):124-135, 2005. Google Scholar
  24. Ken-ichi Kawarabayashi and Mikkel Thorup. The minimum k-way cut of bounded size is fixed-parameter tractable. In Proc. FOCS 2011, pages 160-169. IEEE Computer Soc., Los Alamitos, CA, 2011. Google Scholar
  25. Philip N. Klein, Serge A. Plotkin, Satish Rao, and Éva Tardos. Approximation algorithms for Steiner and directed multicuts. J. Algorithms, 22(2):241-269, 1997. Google Scholar
  26. Jochen Könemann, Stefano Leonardi, Guido Schäfer, and Stefan H. M. van Zwam. A group-strategyproof cost sharing mechanism for the Steiner Forest game. SIAM J. Comput., 37(5):1319-1341, 2008. Google Scholar
  27. Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk, and Magnus Wahlström. Fixed-parameter tractability of multicut in directed acyclic graphs. In Proc. ICALP 2012, volume 7391 of Lecture Notes Comput. Sci., pages 581-593. Springer, Berlin, 2012. Google Scholar
  28. Stefan Kratsch and Magnus Wahlström. Representative sets and irrelevant vertices: New tools for kernelization. In Proc. FOCS 2012, pages 450-459, 2012. Google Scholar
  29. Lap Chi Lau. An approximate max-Steiner-tree-packing min-Steiner-cut theorem. Combinatorica, 27(1):71-90, 2007. Google Scholar
  30. Dániel Marx. Parameterized graph separation problems. Theoret. Comput. Sci., 351(3):394-406, 2006. Google Scholar
  31. Dániel Marx, Barry O'Sullivan, and Igor Razgon. Finding small separators in linear time via treewidth reduction. ACM Trans. Algorithms, 9(4):30:1-30:35, October 2013. Google Scholar
  32. Dániel Marx and Igor Razgon. Fixed-parameter tractability of multicut parameterized by the size of the cutset. In Proc. STOC 2011, pages 469-478, New York, NY, USA, 2011. ACM. Google Scholar
  33. Mingyu Xiao. Simple and improved parameterized algorithms for multiterminal cuts. Theory Comput. Syst., 46(4):723-736, 2010. Google Scholar
  34. Mihalis Yannakakis, Paris C. Kanellakis, Stavros S. Cosmadakis, and Christos H. Papadimitriou. Cutting and partitioning a graph after a fixed pattern (extended abstract). In Proc. ICALP 1983, volume 154 of Lecture Notes Comput. Sci., pages 712-722, London, UK, UK, 1983. Springer-Verlag. Google Scholar
  35. Bo Yu and Joseph Cheriyan. Approximation algorithms for feasible cut and multicut problems. In Proc. ESA 1995, volume 979 of Lecture Notes Comput. Sci., pages 394-408. Springer, Berlin, 1995. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact