{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreihhldyoqfmeuoxmf3c2atlnit3u634urkfwxzcechxwljlptn2cou",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mkmefp5iu362"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2604.25585v1",
  "publishedAt": "2026-04-29T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Afrouz Jabal Ameli",
    "Tomohiro Koana",
    "Jesper Nederlof",
    "Shengzhe Wang"
  ],
  "textContent": "**Authors:** Afrouz Jabal Ameli, Tomohiro Koana, Jesper Nederlof, Shengzhe Wang\n\nThe 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"
}