Highly Connected Steiner Subgraph -- Parameterized Algorithms and Applications to Hitting Set Problems
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912626641993728 |
|---|---|
| author | Eiben, Eduard Majumdar, Diptapriyo Ramanujan, M. S. |
| author_facet | Eiben, Eduard Majumdar, Diptapriyo Ramanujan, M. S. |
| contents | Given a simple connected undirected graph G = (V, E), a set X \subseteq V(G), and integers k and p, STEINER SUBGRAPH EXTENSION problem asks if there exists a set S \supseteq X with at most k vertices such that G[S] is p-edge-connected. This is a natural generalization of a well-studied problem STEINER TREE (set p=1 and X as the set of all terminals). In this paper, we initiate the study of STEINER SUBGRAPH EXTENSION from the perspective of parameterized complexity and give a fixed-parameter algorithm parameterized by k and p on graphs of bounded degeneracy. In case we remove the assumption of the input graph being bounded degenerate, then the STEINER SUBGRAPH EXTENSION problem becomes W[1]-hard. 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 singly exponential-time FPT algorithms for several vertex deletion problem studied in the literature, where the goal is to delete a smallest set of vertices such that (i) the resulting graph belongs to a specific hereditary graph class, and (ii) the deleted set of vertices induces a p-edge-connected subgraph of the input graph. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_02708 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Highly Connected Steiner Subgraph -- Parameterized Algorithms and Applications to Hitting Set Problems Eiben, Eduard Majumdar, Diptapriyo Ramanujan, M. S. Data Structures and Algorithms Discrete Mathematics F.2.2; G.2.2 Given a simple connected undirected graph G = (V, E), a set X \subseteq V(G), and integers k and p, STEINER SUBGRAPH EXTENSION problem asks if there exists a set S \supseteq X with at most k vertices such that G[S] is p-edge-connected. This is a natural generalization of a well-studied problem STEINER TREE (set p=1 and X as the set of all terminals). In this paper, we initiate the study of STEINER SUBGRAPH EXTENSION from the perspective of parameterized complexity and give a fixed-parameter algorithm parameterized by k and p on graphs of bounded degeneracy. In case we remove the assumption of the input graph being bounded degenerate, then the STEINER SUBGRAPH EXTENSION problem becomes W[1]-hard. 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 singly exponential-time FPT algorithms for several vertex deletion problem studied in the literature, where the goal is to delete a smallest set of vertices such that (i) the resulting graph belongs to a specific hereditary graph class, and (ii) the deleted set of vertices induces a p-edge-connected subgraph of the input graph. |
| title | Highly Connected Steiner Subgraph -- Parameterized Algorithms and Applications to Hitting Set Problems |
| topic | Data Structures and Algorithms Discrete Mathematics F.2.2; G.2.2 |
| url | https://arxiv.org/abs/2311.02708 |