License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2023.45
URN: urn:nbn:de:0030-drops-185793
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18579/
Go to the corresponding LIPIcs Volume Portal

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

Finding a Highly Connected Steiner Subgraph and its Applications

pdf-format:
LIPIcs-MFCS-2023-45.pdf (0.8 MB)

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.

BibTeX - Entry

@InProceedings{eiben_et_al:LIPIcs.MFCS.2023.45,
  author =	{Eiben, Eduard and Majumdar, Diptapriyo and Ramanujan, M. S.},
  title =	{{Finding a Highly Connected Steiner Subgraph and its Applications}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{45:1--45:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18579},
  URN =		{urn:nbn:de:0030-drops-185793},
  doi =		{10.4230/LIPIcs.MFCS.2023.45},
  annote =	{Keywords: Parameterized Complexity, Steiner Subgraph Extension, p-edge-connected graphs, Matroids, Representative Families}
}

Keywords: Parameterized Complexity, Steiner Subgraph Extension, p-edge-connected graphs, Matroids, Representative Families
Collection: 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Issue Date: 2023
Date of publication: 21.08.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI