{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:39:40Z","timestamp":1787337580505,"version":"build-2736575974"},"reference-count":69,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/501100001824","name":"Czech Science Foundation","doi-asserted-by":"crossref","award":["GACR no. P202\/12\/G061"],"award-info":[{"award-number":["GACR no. P202\/12\/G061"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Center for FOundations of Modern Computer Science","award":["UNCE\/SCI\/004"],"award-info":[{"award-number":["UNCE\/SCI\/004"]}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N000141110662"],"award-info":[{"award-number":["N000141110662"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["280152"],"award-info":[{"award-number":["280152"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["725978"],"award-info":[{"award-number":["725978"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["2014-CoG 647557"],"award-info":[{"award-number":["2014-CoG 647557"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1053605"],"award-info":[{"award-number":["1053605"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100008510","name":"University of Maryland","doi-asserted-by":"publisher","award":["RASA"],"award-info":[{"award-number":["RASA"]}],"id":[{"id":"10.13039\/100008510","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2020,1]]},"abstract":"<jats:p>Given a vertex-weighted directed graph $G=(V,E)$ and a set $T=\\{t_1, t_2, \\ldots, t_k\\}$ of $k$ terminals, the objective of the Strongly Connected Steiner Subgraph (SCSS) problem is to find a vertex set $H\\subseteq V$ of minimum weight such that $G[H]$ contains a $t_{i}\\rightarrow t_j$ path for each $i\\neq j$. The problem is NP-hard, but Feldman and Ruhl [ SIAM J. Comput., 36 (2006), pp. 543--561] gave a novel $n^{O(k)}$ algorithm for the SCSS problem, where $n$ is the number of vertices in the graph and $k$ is the number of terminals. We explore how much easier the problem becomes on planar directed graphs. Our main algorithmic result is a $2^{O(k)}\\cdot n^{O(\\sqrt{k})}$ algorithm for planar SCSS, which is an improvement of a factor of $O(\\sqrt{k})$ in the exponent over the algorithm of Feldman and Ruhl. Our main hardness result is a matching lower bound for our algorithm: we show that planar SCSS does not have an $f(k)\\cdot n^{o(\\sqrt{k})}$ algorithm for any computable function $f$, unless the exponential time hypothesis (ETH) fails. To obtain our algorithm, we first show combinatorially that there is a minimal solution whose treewidth is $O(\\sqrt{k})$, and then use the dynamic-programming based algorithm for finding bounded-treewidth solutions due to Feldmann and Marx [The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems, preprint, \u016dlhttps:\/\/arxiv.org\/abs\/1707.06808]. To obtain the lower bound matching the algorithm, we need a delicate construction of gadgets arranged in a gridlike fashion to tightly control the number of terminals in the created instance. The following additional results put our upper and lower bounds in context: our $2^{O(k)}\\cdot n^{O(\\sqrt{k})}$ algorithm for planar directed graphs can be generalized to graphs excluding a fixed minor. Additionally, we can obtain this running time for the problem of finding an optimal planar solution even if the input graph is not planar. In general graphs, we cannot hope for such a dramatic improvement over the $n^{O(k)}$ algorithm of Feldman and Ruhl: assuming ETH, SCSS in general graphs does not have an $f(k)\\cdot n^{o(k\/\\log k)}$ algorithm for any computable function $f$. Feldman and Ruhl generalized their $n^{O(k)}$ algorithm to the more general Directed Steiner Network (DSN) problem; here the task is to find a subgraph of minimum weight such that for every source $s_i$ there is a path to the corresponding terminal $t_i$. We show that, assuming ETH, there is no $f(k)\\cdot n^{o(k)}$ time algorithm for DSN on acyclic planar graphs. All our lower bounds hold for the integer weighted edge version, while the algorithm works for the more general unweighted vertex version.<\/jats:p>","DOI":"10.1137\/18m122371x","type":"journal-article","created":{"date-parts":[[2020,3,25]],"date-time":"2020-03-25T11:21:01Z","timestamp":1585135261000},"page":"318-364","source":"Crossref","is-referenced-by-count":9,"title":["Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions)"],"prefix":"10.1137","volume":"49","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6098-7770","authenticated-orcid":true,"given":"Rajesh H.","family":"Chitnis","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andreas E.","family":"Feldmann","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"MohammadTaghi","family":"HajiAghayi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel","family":"Marx","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2020,3,25]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22109"},{"key":"atypb2","first-page":"1028","author":"Bateni M.","year":"2011","journal-title":"Philadelphia"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1145\/2027216.2027219"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2012.10.007"},{"key":"atypb5","first-page":"67","author":"Bj\u00f6rklund A.","year":"2007","journal-title":"New York"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1145\/2973749"},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"H. L. Bodlaender, D. Lokshtanov, and E. Penninkx,\n                      \n                        Planar capacitated dominating set is\n                        W\n                        [1]-hard\n                      \n                      , in Parameterized and Exact Computation, 4th International Workshop, IWPEC 2009, Copenhagen, Denmark, 2009, Revised Selected Papers, Springer, Berlin, 2009, pp. 50-60,https:\/\/doi.org\/10.1007\/978-3-642-11269-0_4.","DOI":"10.1007\/978-3-642-11269-0_4"},{"key":"atypb8","unstructured":"\u00c9. Bonnet, P. Giannopoulos, and M. Lampis,\n                      On the parameterized complexity of red-blue points separation\n                      , in Proceedings of the 12th International Symposium on Parameterized and Exact Computation, IPEC 2017, Wadern, Germany, Schloss Dagstuhl, Vienna, Austria, 2017, 8,https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2017.8."},{"key":"atypb9","first-page":"10","volume":"19","author":"Bonnet \u00c9.","year":"2016","journal-title":"Schloss Dagstuhl"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2016.11.016"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1145\/1541885.1541892"},{"key":"atypb12","first-page":"10","volume":"23","author":"Bringmann K.","year":"2016","journal-title":"Schloss Dagstuhl"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-1346-y"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1042"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.04.007"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-016-0145-8"},{"key":"atypb17","unstructured":"R. Chitnis and A. E. Feldmann,\n                      FPT inapproximability of directed cut and connectivity problems\n                      , in Proceedings of the 14th International Symposium on Parmeterized and Exact Computation, IPEC 2019, Wadern, Germany, Schloss, Dagstuhl, 2019, 8,https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2019.8."},{"key":"atypb18","first-page":"10","volume":"20","author":"Chitnis R.","year":"2018","journal-title":"Schloss Dagstuhl"},{"key":"atypb19","first-page":"1782","author":"Chitnis R. H.","year":"2014","journal-title":"Philadelphia"},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"R. Curticapean, H. Dell, and D. Marx,\n                      Homomorphisms are a good basis for counting small subgraphs\n                      , in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, 2017, ACM, New York, pp. 210-223,https:\/\/doi.org\/10.1145\/3055399.3055502.","DOI":"10.1145\/3055399.3055502"},{"key":"atypb21","first-page":"130","author":"Curticapean R.","year":"2014","journal-title":"NJ"},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"R. Curticapean and M. Xia,\n                      Parameterizing the permanent: Genus, apices, minors, evaluation mod 2k\n                      , in Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, IEEE, Piscataway, NJ, 2015, pp. 994-1009,https:\/\/doi.org\/10.1109\/FOCS.2015.65.","DOI":"10.1109\/FOCS.2015.65"},{"key":"atypb23","doi-asserted-by":"crossref","unstructured":"M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh,\n                      Parameterized Algorithms\n                      , Springer, Cham, Switzerland, 2015,https:\/\/doi.org\/10.1007\/978-3-319-21275-3.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1145\/1101821.1101823"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm033"},{"key":"atypb26","first-page":"682","author":"Demaine E. D.","year":"2005","journal-title":"Philadelphia"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1145\/2601070"},{"key":"atypb28","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows,\n                      Parameterized Complexity\n                      , Monogr. Comput. Sci., Springer, New York, 1999,https:\/\/doi.org\/10.1007\/978-1-4612-0515-9.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010302"},{"key":"atypb30","first-page":"10","volume":"26","author":"Dvor\u00e1k P.","year":"2018","journal-title":"Schloss Dagstuhl"},{"key":"atypb31","first-page":"10","volume":"25","author":"Eiben E.","year":"2019","journal-title":"Schloss Dagstuhl"},{"key":"atypb32","first-page":"626","author":"Eisenstat D.","year":"2012","journal-title":"Philadelphia"},{"key":"atypb33","doi-asserted-by":"crossref","unstructured":"R. Enciso, M. R. Fellows, J. Guo, I. A. Kanj, F. A. Rosamond, and O. Such\u00fd,\n                      What makes equitable connected partition easy\n                      , in Parameterized and Exact Computation, 4th International Workshop, IWPEC 2009, Copenhagen, Denmark, 2009, Revised Selected Papers, Springer, Berlin, 2009, pp. 122-133,https:\/\/doi.org\/10.1007\/978-3-642-11269-0_10.","DOI":"10.1007\/978-3-642-11269-0_10"},{"key":"atypb34","unstructured":"D. Eppstein and D. Lokshtanov,\n                      The parameterized complexity of finding point sets with hereditary properties\n                      , in Proceedings of the 13th International Symposium on Parameterized and Exact Computation, IPEC 2018, Helsinki, Finland, Wadern, Germany, Schloss Dagstuhl, 2018, 11,https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2018.11."},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704441241"},{"key":"atypb36","unstructured":"A. E. Feldmann and D. Marx,\n                      The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems\n                      ,https:\/\/arxiv.org\/abs\/1707.06808, 2017."},{"key":"atypb37","doi-asserted-by":"crossref","unstructured":"J. Flum and M. Grohe,\n                      Parameterized Complexity Theory\n                      , Texts Theoret. Comput. Sci. EATCS Ser., Springer, Berlin, 2006,https:\/\/doi.org\/10.1007\/3-540-29953-X.","DOI":"10.1007\/3-540-29953-X"},{"key":"atypb38","first-page":"10","volume":"39","author":"Fomin F. V.","year":"2016","journal-title":"Schloss Dagstuhl"},{"key":"atypb39","doi-asserted-by":"crossref","unstructured":"F. V. Fomin, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh,\n                      Subexponential parameterized algorithms for planar and apex-minor-free graphs via low treewidth pattern covering\n                      , in Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, New Brunswick, NJ, IEEE, Piscataway, NJ, 2016, pp. 515-524,https:\/\/doi.org\/10.1109\/FOCS.2016.62.","DOI":"10.1109\/FOCS.2016.62"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1145\/504794.504798"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9685-8"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1137\/100794560"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010203"},{"key":"atypb44","first-page":"585","author":"Halperin E.","year":"2003","journal-title":"New York"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2012.04.004"},{"key":"atypb48","doi-asserted-by":"publisher","DOI":"10.1137\/15M103618X"},{"key":"atypb49","first-page":"85","author":"Karp R. M.","year":"1972","journal-title":"Boston"},{"key":"atypb50","first-page":"569","author":"Klein P. N.","year":"2012","journal-title":"Berlin"},{"key":"atypb51","first-page":"1812","author":"Klein P. N.","year":"2014","journal-title":"Philadelphia"},{"key":"atypb52","first-page":"1477","volume":"12","author":"Levin A.","year":"1971","journal-title":"Sov. Math. Dokl."},{"key":"atypb53","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(92)90258-C"},{"key":"atypb54","first-page":"2181","author":"Lokshtanov D.","year":"2020","journal-title":"Philadelphia"},{"key":"atypb55","first-page":"424","author":"Lokshtanov D.","year":"2012","journal-title":"Schloss Dagstuhl"},{"key":"atypb56","doi-asserted-by":"crossref","unstructured":"D. Marx,\n                      On the optimality of planar and geometric approximation schemes\n                      , in Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007, Providence, RI, IEEE Computer Society, Los Alamitos, CA, 2007, pp. 338-348.","DOI":"10.1109\/FOCS.2007.26"},{"key":"atypb57","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2010.v006a005"},{"key":"atypb58","first-page":"677","author":"Marx D.","year":"2012","journal-title":"Berlin"},{"key":"atypb59","first-page":"865","author":"Marx D.","year":"2015","journal-title":"Berlin"},{"key":"atypb60","first-page":"474","author":"Marx D.","year":"2018","journal-title":"NJ"},{"key":"atypb61","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(97)00010-3"},{"key":"atypb62","doi-asserted-by":"crossref","unstructured":"R. Niedermeier,\n                      Invitation to Fixed-Parameter Algorithms\n                      , Oxford University Press, Oxford, 2006,https:\/\/doi.org\/10.1093\/ACPROF:OSO\/9780198566076.001.0001.","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"atypb63","first-page":"353","author":"Pilipczuk M.","year":"2013","journal-title":"Dagstuhl"},{"key":"atypb64","doi-asserted-by":"publisher","DOI":"10.1145\/3201775"},{"key":"atypb65","doi-asserted-by":"publisher","DOI":"10.1109\/90.532865"},{"key":"atypb66","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1994.1073"},{"key":"atypb67","doi-asserted-by":"publisher","DOI":"10.1109\/49.564132"},{"key":"atypb68","first-page":"257","author":"Such\u00fd O.","year":"2016","journal-title":"Berlin"},{"key":"atypb69","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230170203"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/18M122371X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:18:48Z","timestamp":1787336328000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/18M122371X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1]]},"references-count":69,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["10.1137\/18M122371X"],"URL":"https:\/\/doi.org\/10.1137\/18m122371x","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1]]}}}