New Parameterized and Exact Exponential Time Algorithms for Strongly Connected Steiner Subgraph
Afrouz Jabal Ameli, Tomohiro Koana, Jesper Nederlof, Shengzhe Wang · 2026
Read New Parameterized and Exact Exponential Time Algorithms for Strongly Connected Steiner Subgraph by Afrouz Jabal Ameli, Tomohiro Koana, Jesper Nederlof, Shengzhe Wang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-25585.txt.
Introduction
Jabal Ameli and three colleagues give new algorithms for the Strongly Connected Steiner Subgraph problem: finding a smallest subgraph strongly connecting a set of terminals. Their main result runs in time exponential in treewidth times a polynomial factor, given a tree decomposition of that width. That is the first such time for strong connectivity. They also give an exact exponential-time algorithm in vertex count for general directed graphs. Finally, no polynomial kernel exists for vertex cover size unless the polynomial hierarchy collapses. The spanning variant does admit one.
Catalog record
| CREATOR | Afrouz Jabal Ameli, Tomohiro Koana, Jesper Nederlof, Shengzhe Wang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 55092 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.25585
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
New Parameterized and Exact Exponential Time Algorithms for Strongly Connected Steiner Subgraph Thanks: AJA,JN and SW are supported by the project COALESCE that has received funding from the European Research Council (ERC), grant agreement No 853234. Afrouz Jabal Ameli, Tomohiro Koana, Jesper Nederlof, Shengzhe Wang Abstract The Strongly Connected Steiner Subgraph (SCSS) problem is a well-studied network design problem that asks for a minimum subgraph that strongly connects a given set of terminals. In this paper, we present several new algorithmic and complexity results for SCSS. As our main result, we show that SCSS can be solved in time 17 tw n O ( 1 ) 17^{\tw}n^{O(1)} on directed graphs with n n vertices when a tree decomposition of the underlying graph of width tw \tw is provided. This improves over a natural tw O ( tw ) n O ( 1 ) \tw^{O(\tw)}n^{O(1)} time algorithm, and is the first algorithm with this kind of running time for a problem involving strong connectivity. Second, we give an exact exponential-time algorithm that solves SCSS in 2 n n O ( 1 ) 2^{n}n^{O(1)} time, improving the known bounds for general directed graphs. Finally, we investigate kernelization with respect to vertex cover. We prove that SCSS does not admit a polynomial kernel when parameterized by the size of a vertex cover, unless the polynomial hierarchy collapses. In contrast, we show that the closely related Strongly Connected Spanning Subgraph problem does admit a polynomial kernel under the same parameterization. 1 Introduction The Steiner Tree problem is one of the earliest and most fundamental problems in combinatorial optimization: Given an undirected graph G=(V,E) along with a set T\subseteq V of terminals, the objective is to find a subgraph of G with the minimum number of edges that connects all the terminals with each other. Accordingly, the problem is called Steiner Tree since this graph can be assumed to be a tree. The parameterized complexity of the problem has been studied already since the 1970s, when Dreyfus and Wagner showed that the problem can be solved in O^{*}(3^{|T|}) time, 1 1 1 We use the O^{*}() notation to hide factors polynomial in the input size. and hence proved it to be fixed parameter tractable when parameterized by the number of terminals. Parameterized by the number of vertices of G , there is an O^{*}(1.36^{n}) -time algorithm [ 18 ] . Another important parameter for Steiner Tree is the treewidth of the input graph G , which measures how tree-like G is. A simple dynamic programming algorithm (cf e.g. [ 12 , Section 7.3.3] ) shows that an instance of Steiner Tree can be solved in O^{*}(\tw^{\tw}) time when a tree decomposition of G of width \tw is given. 2 2 2 This is a standard assumption made when parameterized by the treewidth of the input graph, and hence will not be explicitly stated in this paper. The \tw^{\tw} dependency here comes from the apparent need to store the connectivity pattern of partial solutions. However, in [ 14 ] it was shown that storing all such patterns is not needed and that, somewhat surprisingly, this running time can be improved to O^{*}(2^{O(\tw)}) at the cost of randomization. This was later derandomized in a follow-up paper to the conference version of [ 14 ] , namely [ 8 ] . Directed and undirected generalizations of Steiner Tree , such as Directed Steiner Network , Group Steiner Tree , and Steiner Forest , have also been studied extensively under these parameters. Examples include Steiner Forest parameterized by treewidth or vertex cover [ 16 ] , Group Steiner Tree parameterized by treewidth [ 10 ] , and Directed Steiner Tree parameterized by the treewidth of the solution network [ 17 ] . The most direct directed analogue of Steiner Tree is the following problem: Strongly Connected Steiner Subgraph (SCSS) Input: A directed graph D=(V,A) , set of terminals T , and integer t . Question: A set X\subseteq A such that |X|\leq t and for each u,v\in T there is a uv -path formed by arcs of X . We are interested in finding out which results that hold for Steiner Tree translate to the directed setting of SCSS (and its variants). Since a solution of SCSS need not be a tree, the problem is typically more complex than its undirected counterpart. Recall that, Steiner Tree is FPT, whereas SCSS is W[1]-hard [ 23 ] and hence probably not FPT. On the positive side, the problem can be solved in n^{O(|T|)} time, i.e., it is XP parameterized by |T| . The complexity of SCSS has been studied extensively from several perspectives. For example, in the setting of planar graphs, parameterized sub-exponential time algorithms are known for the problem [ 11 , 17 ] . From the approximation point of view, there is an O(\log^{2}n) -approximation algorithm for SCSS , and this is tight in the sense that it is hard to approximate with factor O(\log^{2-\varepsilon}n) [ 24 ] . Problems Related to SCSS . To place our results in context, we also describe three related problems. See Figure 1 for the relationships among them. First, setting T=V in SCSS , we obtain the following problem: Strongly Connected Spanning Subgraph (SCSpS) Input: A directed graph D=(V,A) , and an integer t . Question: A set X\subseteq A such that |X|\leq t and (V,X) is strongly connected. An instance of SCSpS is automatically a NO-instance if D is not strongly connected. If we relax the requirement that D itself be strongly connected, we obtain the following problem: Minimum Equivalent Graph (MEG) Input: A directed graph D=(V,E) , and an integer t . Question: A set X\subseteq E such that |X|\leq t and for each uv -path in D , there is a uv -path in (V,X) . The problem is well-motivated, since one often wants to preserve all connectivity properties while working with a sparser network. We refer to [ 2 , Chapter 12] for more information on SCSpS and MEG . It is shown in [ 2 , Section 2.3] that a given instance (D,t) of MEG can be solved in polynomial time provided that, for each strongly connected component C_{i} of D , one is given a minimum-cardinality spanning subdigraph of D[C_{i}] . Hence an O^{*}(c^{n}) -time (respectively, O^{*}(c^{\tw}) -time) algorithm for SCSpS implies an O^{*}(c^{n}) -time (respectively, O^{*}(c^{\tw}) -time) algorithm for MEG . In [ 20 ] it was shown that SCSpS (and hence, MEG ) can be solved on n -vertex graphs in time O(2^{4\omega n}mn) , where \omega denotes the matrix multiplication constant. A randomized O^{*}(4^{n}) -time algorithm is given in [ 15 ] . We will show that our methods can also be used to address 2 -connectivity constraints in undirected graphs via the following problem: 2 -Edge Connected Spanning Subgraph ( 2 -ECSS) Input: An undirected graph G=(V,E) and an integer t . Question: A set X\subseteq E such that |X|\leq t and (V,X) is 2 -edge connected. Note that 2 -ECSS can be reduced to SCSpS by replacing each edge with an arc in both directions. 3 3 3 We spell this out in Appendix A