pith. sign in

arxiv: 2604.25585 · v1 · submitted 2026-04-28 · 💻 cs.DS

New Parameterized and Exact Exponential Time Algorithms for Strongly Connected Steiner Subgraph

Afrouz Jabal Ameli , Tomohiro Koana , Jesper Nederlof , Shengzhe Wang This is my paper

Pith reviewed 2026-05-07 15:03 UTC · model grok-4.3

classification 💻 cs.DS
keywords Strongly Connected Steiner Subgraphtreewidthparameterized algorithmsexact exponential algorithmskernelizationdirected graphsnetwork design
0
0 comments X

The pith

SCSS on directed graphs is solvable in 17^tw n^O(1) time given a tree decomposition of width tw for the underlying undirected graph.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops faster algorithms for finding a minimum subgraph that strongly connects a given set of terminals in a directed graph. Its main contribution is a dynamic programming procedure that runs in time 17 to the power of the treewidth times a polynomial, which is the first single-exponential bound of this form for any strong-connectivity problem. The same work supplies a 2^n exact algorithm that improves on prior general-case bounds and proves that SCSS admits no polynomial kernel when parameterized by vertex cover size, while the related spanning version does. These results matter because network design tasks often involve sparse or low-treewidth instances where tree decompositions are available or cheap to compute.

Core claim

SCSS can be solved in time 17^{tw} n^{O(1)} on directed graphs with n vertices when a tree decomposition of the underlying graph of width tw is provided. This improves over a natural tw^{O(tw)} n^{O(1)} time algorithm and is the first algorithm with single-exponential dependence on treewidth for a problem involving strong connectivity. An exact algorithm solves SCSS in 2^n n^{O(1)} time on general directed graphs, and SCSS has no polynomial kernel under vertex-cover parameterization unless the polynomial hierarchy collapses, whereas Strongly Connected Spanning Subgraph does admit one.

What carries the argument

Dynamic programming over a tree decomposition of the underlying undirected graph whose states track a constant number of connectivity configurations per bag sufficient to enforce strong connectivity among the terminals.

If this is right

  • Instances of SCSS whose underlying graphs have small treewidth become solvable in time single-exponential in that width rather than double-exponential.
  • The same DP framework supplies the first single-exponential treewidth algorithm for any directed-graph problem whose correctness depends on strong connectivity.
  • General directed instances of SCSS without bounded treewidth can be solved exactly in 2^n n^O(1) time, improving earlier exponential-time bounds.
  • SCSS is unlikely to admit a polynomial kernel when parameterized by vertex-cover size, while the closely related Strongly Connected Spanning Subgraph problem does admit one.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar single-exponential DP techniques might extend to other directed connectivity problems once their state spaces are shown to be bounded by a small constant.
  • The contrast between the Steiner and spanning variants under vertex-cover parameterization suggests that terminal-specific constraints often destroy kernelization possibilities.
  • In practice, the treewidth algorithm could be combined with heuristics that compute or approximate tree decompositions for real-world directed networks of moderate density.
  • It remains open whether the base 17 can be lowered by a more refined state encoding or by exploiting additional structure in the terminal set.

Load-bearing premise

It is possible to design a dynamic programming state that enforces the strong-connectivity requirement among terminals using only 17 states per bag without needing a larger exponential base.

What would settle it

A concrete directed graph together with its tree decomposition of small width for which the minimum SCSS solution cannot be recovered by any DP that uses at most 17 states per bag.

Figures

Figures reproduced from arXiv: 2604.25585 by Afrouz Jabal Ameli, Jesper Nederlof, Shengzhe Wang, Tomohiro Koana.

Figure 1
Figure 1. Figure 1: The four problems Strongly Connected Steiner Subgraph (SCSS), Strongly Connected Spanning Subgraph (SCSpS), Minimum Equivalent Graph (MEG) and 2- Edge Connected Spanning Subgraph (2-ECSS) studied in this paper. An arrow denotes the relation “can be efficiently reduced to”, and hence an algorithm for SCSS implies an algo￾rithm for all other problems with comparable run time. 2-Edge Connected Spanning Subgra… view at source ↗
read the original 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^{\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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper presents new algorithmic results for the Strongly Connected Steiner Subgraph (SCSS) problem on directed graphs. Its main claim is a dynamic programming algorithm solving SCSS in 17^{tw} n^{O(1)} time given a tree decomposition of width tw of the underlying undirected graph, improving on the natural tw^{O(tw)} n^{O(1)} bound and providing the first single-exponential dependence on tw for a strong-connectivity problem. It also gives a 2^n n^{O(1)} exact exponential-time algorithm for general directed graphs and proves that SCSS admits no polynomial kernel parameterized by vertex cover size (unless the polynomial hierarchy collapses), while the related Strongly Connected Spanning Subgraph problem does admit one.

Significance. If the central 17^{tw} bound holds, the result would be significant for parameterized algorithms on directed graphs, as it demonstrates that strong-connectivity constraints can be enforced via DP over an undirected tree decomposition without super-constant blowup in the base. This is the first such single-exponential result for strong connectivity and could serve as a template for other directed connectivity problems. The exact algorithm offers a modest improvement over prior bounds, and the kernelization results provide a clean complexity separation between SCSS and its spanning variant under vertex-cover parameterization.

minor comments (3)
  1. The abstract states that the 17^{tw} algorithm is 'the first algorithm with this kind of running time for a problem involving strong connectivity,' but the introduction should explicitly cite and contrast with all prior single-exponential results for related directed connectivity problems (e.g., directed Steiner tree or reachability variants) to substantiate the novelty claim.
  2. In the treewidth DP section, the state space achieving the factor of 17 should include a brief table or explicit enumeration of the 17 configurations per bag to aid verification of the constant.
  3. The kernelization section for vertex cover should clarify whether the no-kernel proof for SCSS relies on the same reduction as prior work or introduces a new gadget; a short comparison paragraph would strengthen the presentation.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript and for recommending acceptance. We appreciate the accurate summary of our results on the single-exponential treewidth algorithm for SCSS, the exact exponential-time algorithm, and the kernelization separation between SCSS and Strongly Connected Spanning Subgraph under vertex-cover parameterization.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained algorithmic construction

full rationale

The paper's central results consist of an explicit dynamic-programming algorithm on tree decompositions (with a concrete state space of size 17^tw that enforces strong connectivity via bag transitions), a 2^n exact algorithm via standard subset enumeration, and a kernelization lower bound proved via standard cross-composition from an NP-hard problem. None of these reduce by definition or self-citation to their own inputs; the 17^tw bound is obtained by direct counting of valid configurations rather than fitting or renaming. Self-citations, if present, are not load-bearing for the new bounds. The derivation chain is therefore independent and falsifiable by inspection of the stated recurrences and correctness proofs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The results rest on standard techniques from parameterized complexity and exact algorithms; the kernelization lower bound invokes the standard assumption that the polynomial hierarchy does not collapse.

axioms (1)
  • domain assumption The polynomial hierarchy does not collapse to a finite level
    Invoked for the no-polynomial-kernel result under vertex cover parameterization.

pith-pipeline@v0.9.0 · 5535 in / 1236 out tokens · 51368 ms · 2026-05-07T15:03:49.021422+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

34 extracted references · 34 canonical work pages

  1. [1]

    Agrawal, P

    A. Agrawal, P. Misra, F. Panolan, and S. Saurabh. Fast exact algorithms for survivable network design with uniform requirements.Algorithmica, 84(9):2622–2641, 2022. [pp. 3 and 16.]

    work page 2022

  2. [2]

    Bang-Jensen and G

    J. Bang-Jensen and G. Z. Gutin.Digraphs - theory, algorithms and applications, second edition. Springer, 2002. [pp. 2 and 12.]

    work page 2002

  3. [3]

    Berger and M

    A. Berger and M. Grigni. Minimum weight 2-edge-connected spanning subgraphs in planar graphs. In L. Arge, C. Cachin, T. Jurdzinski, and A. Tarlecki, editors,Automata, Languages and Programming, 34th International Colloquium, ICALP 2007, Wroclaw, Poland, July 9- 13, 2007, Proceedings, Lecture Notes in Computer Science, pages 90–101. Springer, 2007. [p. 3.]

    work page 2007

  4. [4]

    Bj¨ orklund

    A. Bj¨ orklund. Determinant sums for undirected Hamiltonicity.SIAM J. Comput., 43(1):280–299, 2014. [p. 17.]

    work page 2014

  5. [5]

    Bj¨ orklund, T

    A. Bj¨ orklund, T. Husfeldt, P. Kaski, and M. Koivisto. Fourier meets M¨ obius: Fast subset convolution. InProceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11–13, 2007, pages 67–74. ACM, 2007. [p. 4.]

    work page 2007

  6. [6]

    Bj¨ orklund, P

    A. Bj¨ orklund, P. Kaski, and I. Koutis. Directed Hamiltonicity and out-branchings via generalized laplacians. In I. Chatzigiannakis, P. Indyk, F. Kuhn, and A. Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, Warsaw, Poland, July 10-14, 2017, LIPIcs, pages 91:1–91:14. Schloss Dagstuhl - Leibniz- Zentrum...

    work page 2017

  7. [7]

    Blazej, P

    V. Blazej, P. Choudhary, D. Knop, S. Schierreich, O. Such´ y, and T. Valla. On polyno- mial kernels for Traveling Salesperson Problem and its generalizations. In S. Chechik, G. Navarro, E. Rotenberg, and G. Herman, editors,30th Annual European Symposium on Algorithms, ESA 2022, Berlin/Potsdam, Germany, September 5-9, 2022, LIPIcs, pages 22:1–22:16. Schlos...

    work page 2022

  8. [8]

    H. L. Bodlaender, M. Cygan, S. Kratsch, and J. Nederlof. Deterministic single exponen- tial time algorithms for connectivity problems parameterized by treewidth.Inf. Comput., 243:86–111, 2015. [pp. 2 and 3.]

    work page 2015

  9. [9]

    Bosch-Calvo, M

    M. Bosch-Calvo, M. Garg, F. Grandoni, F. Hommelsheim, A. J. Ameli, and A. Lindermayr. A 5/4-approximation for two-edge connectivity. InProceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC ’25, page 653–664, New York, NY, USA, 2025. Association for Computing Machinery. [p. 3.]

    work page 2025

  10. [10]

    Chalermsook, S

    P. Chalermsook, S. Das, B. Laekhanukit, and D. Vaz. Beyond metric embedding: Ap- proximating group Steiner trees on bounded treewidth graphs. In P. N. Klein, editor, 17 Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 737–751. SIAM,

    work page 2017

  11. [11]

    R. H. Chitnis, A. E. Feldmann, M. T. Hajiaghayi, and D. Marx. Tight bounds for pla- nar strongly connected Steiner subgraph with fixed number of terminals (and extensions). SIAM J. Comput., 49(2):318–364, 2020. [p. 2.]

    work page 2020

  12. [12]

    Cygan, F

    M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh.Parameterized Algorithms. Springer, 2015. [pp. 1 and 11.]

    work page 2015

  13. [13]

    Cygan, J

    M. Cygan, J. Nederlof, M. Pilipczuk, M. Pilipczuk, J. M. M. van Rooij, and J. O. Woj- taszczyk. Solving connectivity problems parameterized by treewidth in single exponential time. In2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22–25, 2011, pages 150–159. IEEE Computer Society, 2011. [p. 4.]

    work page 2011

  14. [14]

    Cygan, J

    M. Cygan, J. Nederlof, M. Pilipczuk, M. Pilipczuk, J. M. M. van Rooij, and J. O. Woj- taszczyk. Solving connectivity problems parameterized by treewidth in single exponential time.ACM Trans. Algorithms, 18(2):17:1–17:31, 2022. [pp. 1, 2, 3, and 5.]

    work page 2022

  15. [15]

    Eiben, T

    E. Eiben, T. Koana, and M. Wahlstr¨ om. Determinantal sieving.TheoretiCS, 4:Article 21,

    work page

  16. [16]

    A. E. Feldmann and M. Lampis. Parameterized algorithms for Steiner forest in bounded width graphs.ACM Trans. Algorithms, 21(4):47:1–47:26, 2025. [pp. 2 and 4.]

    work page 2025

  17. [17]

    A. E. Feldmann and D. Marx. The complexity landscape of fixed-parameter directed Steiner network problems.ACM Trans. Comput. Theory, 15(3-4):4:1–4:28, 2023. [p. 2.]

    work page 2023

  18. [18]

    F. V. Fomin, F. Grandoni, D. Kratsch, D. Lokshtanov, and S. Saurabh. Computing optimal Steiner trees in polynomial space.Algorithmica, 65(3):584–604, 2013. [p. 1.]

    work page 2013

  19. [19]

    F. V. Fomin, T.-N. Le, D. Lokshtanov, S. Saurabh, S. Thomass´ e, and M. Zehavi. Sub- quadratic kernels for implicit 3-hitting set and 3-set packing problems.ACM Trans. Algo- rithms, 15(1):13:1–13:44, 2019. [pp. 4 and 13.]

    work page 2019

  20. [20]

    F. V. Fomin, D. Lokshtanov, F. Panolan, and S. Saurabh. Efficient computation of rep- resentative families with applications in parameterized and exact algorithms.J. ACM, 63(4):29:1–29:60, 2016. [pp. 2, 3, and 4.]

    work page 2016

  21. [21]

    F. V. Fomin, D. Lokshtanov, and S. Saurabh.Kernelization: Theory of Parameterized Preprocessing. Cambridge Monographs on Mathematical Physics. Cambridge University Press, 2019. [p. 15.]

    work page 2019

  22. [22]

    M. Garg, F. Grandoni, and A. J. Ameli. Improved approximation for two-edge-connectivity. In N. Bansal and V. Nagarajan, editors,Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 2368–2410. SIAM, 2023. [p. 3.]

    work page 2023

  23. [23]

    J. Guo, R. Niedermeier, and O. Such´ y. Parameterized complexity of arc-weighted directed Steiner problems. In Y. Dong, D. Du, and O. H. Ibarra, editors,Algorithms and Com- putation, 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009. Proceedings, Lecture Notes in Computer Science, pages 544–553. Springer,

    work page 2009

  24. [24]

    Halperin and R

    E. Halperin and R. Krauthgamer. Polylogarithmic inapproximability.SIAM Journal on Computing, 32(5):1267–1283, 2003. [p. 2.]

    work page 2003

  25. [25]

    Hommelsheim, A

    F. Hommelsheim, A. Lindermayr, and Z. Liu. A better-than-5/4-approximation for two- edge connectivity. In K. G. Larsen and B. Saha, editors,Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, Vancouver, BC, Canada, January 11-14, 2026, pages 1468–1520. SIAM, 2026. [p. 3.]

    work page 2026

  26. [26]

    Kloks.Treewidth, Computations and Approximations, volume 842 ofLecture Notes in Computer Science

    T. Kloks.Treewidth, Computations and Approximations, volume 842 ofLecture Notes in Computer Science. Springer, 1994. [p. 5.]

    work page 1994

  27. [27]

    Kobayashi and T

    Y. Kobayashi and T. Noguchi. An Approximation Algorithm for Two-Edge-Connected Subgraph Problem via Triangle-Free Two-Edge-Cover. In S. Iwata and N. Kakimura, editors,34th International Symposium on Algorithms and Computation (ISAAC 2023), volume 283 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 49:1–49:10, Dagstuhl, Germany, 2023. Sc...

    work page 2023

  28. [28]

    Lokshtanov, D

    D. Lokshtanov, D. Marx, and S. Saurabh. Known algorithms on graphs of bounded treewidth are probably optimal.ACM Trans. Algorithms, 14(2):13:1–13:30, 2018. [p. 16.]

    work page 2018

  29. [29]

    Lokshtanov, F

    D. Lokshtanov, F. Panolan, M. S. Ramanujan, and S. Saurabh. Lossy kernelization. In H. Hatami, P. McKenzie, and V. King, editors,Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 224–237. ACM, 2017. [p. 15.]

    work page 2017

  30. [30]

    Mannens, J

    I. Mannens, J. Nederlof, C. M. F. Swennenhuis, and K. Szil´ agyi. On the parameterized com- plexity of the connected flow and many visits TSP problem. In L. Kowalik, M. Pilipczuk, and P. Rzazewski, editors,Graph-Theoretic Concepts in Computer Science - 47th Interna- tional Workshop, WG 2021, Warsaw, Poland, June 23-25, 2021, Revised Selected Papers, Lectu...

    work page 2021

  31. [31]

    Mulmuley, U

    K. Mulmuley, U. V. Vazirani, and V. V. Vazirani. Matching is as easy as matrix inversion. Comb., 7(1):105–113, 1987. [p. 5.]

    work page 1987

  32. [32]

    Nederlof

    J. Nederlof. Algorithms for np-hard problems via rank-related parameters of matrices. In F. V. Fomin, S. Kratsch, and E. J. van Leeuwen, editors,Treewidth, Kernels, and Algorithms - Essays Dedicated to Hans L. Bodlaender on the Occasion of His 60th Birthday, Lecture Notes in Computer Science, pages 145–164. Springer, 2020. [p. 16.]

    work page 2020

  33. [33]

    Robertson and P

    N. Robertson and P. D. Seymour. Graph minors. III. planar tree-width.J. Comb. Theory B, 36(1):49–64, 1984. [p. 4.]

    work page 1984

  34. [34]

    J. M. M. van Rooij. Fast algorithms for join operations on tree decompositions. In F. V. Fomin, S. Kratsch, and E. J. van Leeuwen, editors,Treewidth, Kernels, and Algorithms - Essays Dedicated to Hans L. Bodlaender on the Occasion of His 60th Birthday, Lecture Notes in Computer Science, pages 262–297. Springer, 2020. [p. 11.] A Reducing2-ECSS to SCSpS Lem...

    work page 2020