The Library
Finding a highly connected Steiner subgraph and its applications
Tools
Eiben, Eduard, Majumdar, Diptapriyo and Ramanujan, M. S. (2023) Finding a highly connected Steiner subgraph and its applications. In: 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Published in: Leibniz International Proceedings in Informatics (LIPIcs), 272 45:1-45:15. doi:10.4230/LIPIcs.MFCS.2023.45 ISSN 1868-8969.
|
PDF
WRAP-finding-highly-connected-Steiner-subgraph-its-applications-2023.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (794Kb) | Preview |
Official URL: https://drops.dagstuhl.de/entities/document/10.423...
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.
Item Type: | Conference Item (Paper) | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
|||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||
Library of Congress Subject Headings (LCSH): | Steiner systems, Matroids , Computer algorithms, Computer science -- Mathematics | |||||||||
Series Name: | Leibniz International Proceedings in Informatics (LIPIcs) | |||||||||
Journal or Publication Title: | Leibniz International Proceedings in Informatics (LIPIcs) | |||||||||
Publisher: | Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik | |||||||||
Place of Publication: | Dagstuhl, Germany | |||||||||
ISSN: | 1868-8969 | |||||||||
Official Date: | 21 August 2023 | |||||||||
Dates: |
|
|||||||||
Volume: | 272 | |||||||||
Page Range: | 45:1-45:15 | |||||||||
DOI: | 10.4230/LIPIcs.MFCS.2023.45 | |||||||||
Status: | Peer Reviewed | |||||||||
Publication Status: | Published | |||||||||
Access rights to Published version: | Open Access (Creative Commons) | |||||||||
Date of first compliant deposit: | 13 December 2023 | |||||||||
Date of first compliant Open Access: | 13 December 2023 | |||||||||
RIOXX Funder/Project Grant: |
|
|||||||||
Conference Paper Type: | Paper | |||||||||
Title of Event: | 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) | |||||||||
Type of Event: | Conference |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year