.png){kind=icon}
.png){kind=icon}
Return
HIGHLY CONNECTED STEINER SUBGRAPH: PARAMETERIZED ALGORITHMS AND APPLICATIONS TO HITTING SET PROBLEMS
.png){kind=icon}
PRE
AI
DOI：10.1137/23M1614031.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Given a simple (connected) undirected graph G, a set X subset of V(G) and integers k and p, the Steiner Subgraph Extension problem asks whether there exists a set S superset of 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. In case we remove the assumption of the graph being bounded degenerate, then Steiner Subgraph Extension 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 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.
Keywords:
parameterized complexity
Steiner Subgraph Extension
matroids
representative families
p-edge-connectivity
Journal
S
IF:
1
Papers:
11
Citations:
2.8K
Organization
View more organizations