Abstract
Given a simple (connected) undirected graph [Formula: see text], a set [Formula: see text] and integers [Formula: see text] and [Formula: see text], the Steiner Subgraph Extension problem asks whether there exists a set [Formula: see text] of at most [Formula: see text] vertices such that [Formula: see text] is a [Formula: see text]-edge-connected subgraph. This problem is a natural generalization of the well-studied Steiner Tree problem (set [Formula: see text] and [Formula: see text] 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 [Formula: see text] and [Formula: see text] 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 [Formula: see text]-edge-connected subgraph of the input graph.
Funding Information
  • Anusandhan National Research Foundation (SRG/2023/001592)
  • Engineering and Physical Sciences Research Council (EP/V007793/1)
  • Engineering and Physical Sciences Research Council (EP/V044621/1)