Highly Connected Steiner Subgraph: Parameterized Algorithms and Applications to Hitting Set Problems
- 6 February 2026
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 40 (1) , 102-133
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.Keywords
All Related Versions
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)
This publication has 29 references indexed in Scilit:
- Generating Faster Algorithms for d-Path Vertex Cover2023
- Fast Exact Algorithms for Survivable Network Design with Uniform RequirementsAlgorithmica, 2022
- Parameterized Algorithms for Steiner Tree and Dominating Set: Bounding the Leafage by the Vertex Leafage2022
- Matroids in Parameterized Complexity and Exact Algorithms2016
- Parameterized Algorithms2015
- On the Parameterized Complexity of Finding Separators with Non-Hereditary PropertiesAlgorithmica, 2014
- Fundamentals of Parameterized Complexity2013
- Forbidden graphs for tree-depthEuropean Journal of Combinatorics, 2012
- A Quartic Kernel for Pathwidth-One Vertex Deletion2010
- The Undirected Feedback Vertex Set Problem Has a Poly(k) KernelLecture Notes in Computer Science, 2006