New Parameterized and Exact Exponential Time Algorithms for Strongly Connected Steiner Subgraph
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917444018241536 |
|---|---|
| author | Ameli, Afrouz Jabal Koana, Tomohiro Nederlof, Jesper Wang, Shengzhe |
| author_facet | Ameli, Afrouz Jabal Koana, Tomohiro Nederlof, Jesper Wang, Shengzhe |
| contents | 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^{\mathrm{tw}} n^{O(1)}$ on directed graphs with $n$ vertices when a tree decomposition of the underlying graph of width $\mathrm{tw}$ is provided. This improves over a natural $\mathrm{tw}^{O(\mathrm{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)}$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_25585 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | New Parameterized and Exact Exponential Time Algorithms for Strongly Connected Steiner Subgraph Ameli, Afrouz Jabal Koana, Tomohiro Nederlof, Jesper Wang, Shengzhe Data Structures and Algorithms 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^{\mathrm{tw}} n^{O(1)}$ on directed graphs with $n$ vertices when a tree decomposition of the underlying graph of width $\mathrm{tw}$ is provided. This improves over a natural $\mathrm{tw}^{O(\mathrm{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)}$ 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. |
| title | New Parameterized and Exact Exponential Time Algorithms for Strongly Connected Steiner Subgraph |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2604.25585 |