Document Open Access Logo

Finding a Highly Connected Steiner Subgraph and its Applications

Authors Eduard Eiben , Diptapriyo Majumdar , M. S. Ramanujan

PDF

File

Thumbnail PDF
PDF
LIPIcs.MFCS.2023.45.pdf
  • Filesize: 0.77 MB
  • 15 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
  • Theory of computation → Dynamic programming
Keywords
  • Parameterized Complexity
  • Steiner Subgraph Extension
  • p-edge-connected graphs
  • Matroids
  • Representative Families

Metrics

Abstract

Given a (connected) undirected graph G, a set X ⊆ V(G) and integers k and p, the Steiner Subgraph Extension problem asks whether there exists a set S ⊇ X of at most k vertices such that G[S] is a p-edge-connected subgraph. This problem is a natural generalization of the well-studied Steiner Tree problem (set p = 1 and X to be the terminals). In this paper, we initiate the study of Steiner Subgraph Extension from the perspective of parameterized complexity and give a fixed-parameter algorithm (i.e., FPT algorithm) parameterized by k and p on graphs of bounded degeneracy (removing the assumption of bounded degeneracy results in W-hardness).
Besides being an independent advance on the parameterized complexity of network design problems, our result has natural applications. In particular, we use our result to obtain new single-exponential FPT algorithms for several vertex-deletion problems studied in the literature, where the goal is to delete a smallest set of vertices such that: (i) the resulting graph belongs to a specified hereditary graph class, and (ii) the deleted set of vertices induces a p-edge-connected subgraph of the input graph.

Cite As Get BibTex

Eduard Eiben, Diptapriyo Majumdar, and M. S. Ramanujan. Finding a Highly Connected Steiner Subgraph and its Applications. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 45:1-45:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.MFCS.2023.45

Author Details

Eduard Eiben
  • Royal Holloway, University of London, Egham, UK
Diptapriyo Majumdar
  • Indraprastha Institute of Information Technology Delhi, New Delhi, India
M. S. Ramanujan
  • University of Warwick, Coventry, UK

Funding

  • Ramanujan, M. S.: Supported by Engineering and Physical Sciences Research Council (EPSRC) grants EP/V007793/1 and EP/V044621/1.

References

  1. Ankit Abhinav, Susobhan Bandopadhyay, Aritra Banik, and Saket Saurabh. Parameterized algorithms for finding highly connected solution. Theor. Comput. Sci., 942:47-56, 2023. Google Scholar
  2. Akanksha Agrawal, Pranabendu Misra, Fahad Panolan, and Saket Saurabh. Fast exact algorithms for survivable network design with uniform requirements. Algorithmica, 84(9):2622-2641, 2022. Google Scholar
  3. MohammadHossein Bateni, Erik D. Demaine, MohammadTaghi Hajiaghayi, and Dániel Marx. A PTAS for planar group steiner tree via spanner bootstrapping and prize collecting. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 570-583. ACM, 2016. Google Scholar
  4. Kevin Burrage, Vladimir Estivill-Castro, Michael R. Fellows, Michael A. Langston, Shev Mac, and Frances A. Rosamond. The undirected feedback vertex set problem has a poly(k) kernel. In Hans L. Bodlaender and Michael A. Langston, editors, Parameterized and Exact Computation, Second International Workshop, IWPEC 2006, Zürich, Switzerland, September 13-15, 2006, Proceedings, volume 4169 of Lecture Notes in Computer Science, pages 192-202. Springer, 2006. Google Scholar
  5. Radovan Cervený and Ondrej Suchý. Faster FPT algorithm for 5-path vertex cover. In Peter Rossmanith, Pinar Heggernes, and Joost-Pieter Katoen, editors, 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, August 26-30, 2019, Aachen, Germany, volume 138 of LIPIcs, pages 32:1-32:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  6. Radovan Cervený and Ondrej Suchý. Generating faster algorithms for d-path vertex cover. CoRR, abs/2111.05896, 2021. URL: https://arxiv.org/abs/2111.05896.
  7. Rajesh Hemant Chitnis, Andreas Emil Feldmann, Mohammad Taghi Hajiaghayi, and Dániel Marx. Tight bounds for planar strongly connected steiner subgraph with fixed number of terminals (and extensions). SIAM J. Comput., 49(2):318-364, 2020. Google Scholar
  8. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  9. Celina M. H. de Figueiredo, Raul Lopes, Alexsander Andrade de Melo, and Ana Silva. Parameterized algorithms for steiner tree and dominating set: Bounding the leafage by the vertex leafage. In Petra Mutzel, Md. Saidur Rahman, and Slamin, editors, WALCOM: Algorithms and Computation - 16th International Conference and Workshops, WALCOM 2022, Jember, Indonesia, March 24-26, 2022, Proceedings, volume 13174 of Lecture Notes in Computer Science, pages 251-262. Springer, 2022. Google Scholar
  10. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. Google Scholar
  11. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. Google Scholar
  12. Zdenek Dvorák, Archontia C. Giannopoulou, and Dimitrios M. Thilikos. Forbidden graphs for tree-depth. Eur. J. Comb., 33(5):969-979, 2012. Google Scholar
  13. Carl Einarson, Gregory Z. Gutin, Bart M. P. Jansen, Diptapriyo Majumdar, and Magnus Wahlström. p-edge/vertex-connected vertex cover: Parameterized and approximation algorithms. J. Comput. Syst. Sci., 133:23-40, 2023. Google Scholar
  14. Andreas Emil Feldmann and Dániel Marx. The complexity landscape of fixed-parameter directed steiner network problems. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, volume 55 of LIPIcs, pages 27:1-27:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. Google Scholar
  15. Andreas Emil Feldmann, Anish Mukherjee, and Erik Jan van Leeuwen. The parameterized complexity of the survivable network design problem. In Karl Bringmann and Timothy Chan, editors, 5th Symposium on Simplicity in Algorithms, SOSA@SODA 2022, Virtual Conference, January 10-11, 2022, pages 37-56. SIAM, 2022. Google Scholar
  16. Michael R. Fellows and Michael A. Langston. On search, decision and the efficiency of polynomial-time algorithms (extended abstract). In David S. Johnson, editor, Proceedings of the 21st Annual ACM Symposium on Theory of Computing, May 14-17, 1989, Seattle, Washington, USA, pages 501-512. ACM, 1989. Google Scholar
  17. Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Efficient computation of representative families with applications in parameterized and exact algorithms. J. ACM, 63(4):29:1-29:60, 2016. Google Scholar
  18. Archontia C. Giannopoulou, Bart M. P. Jansen, Daniel Lokshtanov, and Saket Saurabh. Uniform kernelization complexity of hitting forbidden minors. ACM Trans. Algorithms, 13(3):35:1-35:35, 2017. Google Scholar
  19. Pinar Heggernes, Pim van 't Hof, Dániel Marx, Neeldhara Misra, and Yngve Villanger. On the parameterized complexity of finding separators with non-hereditary properties. Algorithmica, 72(3):687-713, 2015. Google Scholar
  20. Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, and Saket Saurabh. Deterministic truncation of linear matroids. ACM Trans. Algorithms, 14(2):14:1-14:20, 2018. Google Scholar
  21. Dániel Marx, Marcin Pilipczuk, and Michal Pilipczuk. On subexponential parameterized algorithms for steiner tree and directed subset TSP on planar graphs. In Mikkel Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 474-484. IEEE Computer Society, 2018. Google Scholar
  22. Rolf Niedermeier. Invitation to Fixed-Parameter Algorithms. Oxford University Press, 2006. Google Scholar
  23. Zeev Nutov. Parameterized algorithms for node connectivity augmentation problems. CoRR, abs/2209.06695, 2022. URL: https://arxiv.org/abs/2209.06695.
  24. James G. Oxley. Matroid theory. Oxford University Press, 1992. Google Scholar
  25. Fahad Panolan and Saket Saurabh. Matroids in parameterized complexity and exact algorithms. In Encyclopedia of Algorithms, pages 1203-1206. Springer, 2016. Google Scholar
  26. Geevarghese Philip, Venkatesh Raman, and Yngve Villanger. A quartic kernel for pathwidth-one vertex deletion. In Dimitrios M. Thilikos, editor, Graph Theoretic Concepts in Computer Science - 36th International Workshop, WG 2010, Zarós, Crete, Greece, June 28-30, 2010 Revised Papers, volume 6410 of Lecture Notes in Computer Science, pages 196-207, 2010. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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