2026-07-24T08:01:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18579 2024-03-06T11:02:10Z ddc:004 open_access

Finding a Highly Connected Steiner Subgraph and its Applications Eiben, Eduard Majumdar, Diptapriyo Ramanujan, M. S. Parameterized Complexity Steiner Subgraph Extension p-edge-connected graphs Matroids Representative Families 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Eduard Eiben and Diptapriyo Majumdar and M. S. Ramanujan 2023 Is Part Of LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2023.45 urn:nbn:de:0030-drops-185793 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.45 eng https://creativecommons.org/licenses/by/4.0/legalcode