{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:09:40Z","timestamp":1750219780736,"version":"3.41.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"3-4","license":[{"start":{"date-parts":[[2023,12,12]],"date-time":"2023-12-12T00:00:00Z","timestamp":1702339200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ERC","award":["280152"],"award-info":[{"award-number":["280152"]}]},{"name":"ERC Consolidator Grant SYSTEMATICGRAPH","award":["725978"],"award-info":[{"award-number":["725978"]}]},{"DOI":"10.13039\/501100001824","name":"Czech Science Foundation GA\u010cR","doi-asserted-by":"crossref","award":["#19-27871X"],"award-info":[{"award-number":["#19-27871X"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2023,12,31]]},"abstract":"<jats:p>\n            Given a directed graph\n            <jats:italic>G<\/jats:italic>\n            and a list (\n            <jats:italic>s<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            ,\n            <jats:italic>t<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            ), \u2026, (\n            <jats:italic>s<\/jats:italic>\n            <jats:sub>\n              <jats:italic>d<\/jats:italic>\n            <\/jats:sub>\n            ,\n            <jats:italic>t<\/jats:italic>\n            <jats:sub>\n              <jats:italic>d<\/jats:italic>\n            <\/jats:sub>\n            ) of terminal pairs, the\n            <jats:sc>Directed Steiner Network<\/jats:sc>\n            problem asks for a minimum-cost subgraph of\n            <jats:italic>G<\/jats:italic>\n            that contains a directed\n            <jats:italic>s<\/jats:italic>\n            <jats:sub>\n              <jats:italic>i<\/jats:italic>\n            <\/jats:sub>\n            \u2192\n            <jats:italic>t<\/jats:italic>\n            <jats:sub>\n              <jats:italic>i<\/jats:italic>\n            <\/jats:sub>\n            path for every 1\u2264\n            <jats:italic>i<\/jats:italic>\n            \u2264\n            <jats:italic>d<\/jats:italic>\n            . The special case\n            <jats:sc>Directed Steiner Tree<\/jats:sc>\n            (when we ask for paths from a root\n            <jats:italic>r<\/jats:italic>\n            to terminals\n            <jats:italic>t<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            , \u2026,\n            <jats:italic>t<\/jats:italic>\n            <jats:sub>\n              <jats:italic>d<\/jats:italic>\n            <\/jats:sub>\n            ) is known to be fixed-parameter tractable parameterized by the number of terminals, while the special case\n            <jats:sc>Strongly Connected Steiner Subgraph<\/jats:sc>\n            (when we ask for a path from every\n            <jats:italic>t<\/jats:italic>\n            <jats:sub>\n              <jats:italic>i<\/jats:italic>\n            <\/jats:sub>\n            to every other\n            <jats:italic>t<\/jats:italic>\n            <jats:sub>\n              <jats:italic>j<\/jats:italic>\n            <\/jats:sub>\n            ) is known to be W[1]-hard parameterized by the number of terminals. We systematically explore the complexity landscape of directed Steiner problems to fully understand which other special cases are FPT or W[1]-hard. Formally, if \u210b is a class of directed graphs, then we look at the special case of\n            <jats:sc>Directed Steiner Network<\/jats:sc>\n            where the list (\n            <jats:italic>s<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            ,\n            <jats:italic>t<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            ), \u2026, (\n            <jats:italic>s<\/jats:italic>\n            <jats:sub>\n              <jats:italic>d<\/jats:italic>\n            <\/jats:sub>\n            ,\n            <jats:italic>t<\/jats:italic>\n            <jats:sub>\n              <jats:italic>d<\/jats:italic>\n            <\/jats:sub>\n            ) of demands form a directed graph that is a member of \u210b. Our main result is a complete characterization of the classes \u210b resulting in fixed-parameter tractable special cases: we show that if every pattern in \u210b has the combinatorial property of being \u201ctransitively equivalent to a bounded-length caterpillar with a bounded number of extra edges,\u201d then the problem is FPT, and it is W[1]-hard for\n            <jats:italic>every<\/jats:italic>\n            recursively enumerable \u210b not having this property. This complete dichotomy unifies and generalizes the known results showing that\n            <jats:sc>Directed Steiner Tree<\/jats:sc>\n            is FPT [Dreyfus and Wagner,\n            <jats:italic>Networks<\/jats:italic>\n            1971],\n            <jats:sc>\n              <jats:italic>q<\/jats:italic>\n              -Root Steiner Tree\n            <\/jats:sc>\n            is FPT for constant\n            <jats:italic>q<\/jats:italic>\n            [Such\u00fd,\n            <jats:italic>WG<\/jats:italic>\n            2016],\n            <jats:sc>Strongly Connected Steiner Subgraph<\/jats:sc>\n            is W[1]-hard [Guo et\u00a0al.,\n            <jats:italic>SIAM J. Discrete Math.<\/jats:italic>\n            2011], and\n            <jats:sc>Directed Steiner Network<\/jats:sc>\n            is solvable in polynomial-time for constant number of terminals [Feldman and Ruhl,\n            <jats:italic>SIAM J. Comput.<\/jats:italic>\n            2006], and moreover reveals a large continent of tractable cases that were not known before.\n          <\/jats:p>\n          <jats:p\/>","DOI":"10.1145\/3580376","type":"journal-article","created":{"date-parts":[[2023,6,6]],"date-time":"2023-06-06T19:10:10Z","timestamp":1686078610000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems"],"prefix":"10.1145","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6229-5332","authenticated-orcid":false,"given":"Andreas Emil","family":"Feldmann","sequence":"first","affiliation":[{"name":"University of Sheffield, UK"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5686-8314","authenticated-orcid":false,"given":"D\u00e1niel","family":"Marx","sequence":"additional","affiliation":[{"name":"CISPA Helmholtz Center for Information Security, Germany"}]}],"member":"320","published-online":{"date-parts":[[2023,12,12]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792236237"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1137\/090771429"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9491-8"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_8"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/2027216.2027219"},{"key":"e_1_3_2_7_2","first-page":"116","article-title":"Some classes of graphs with bounded treewidth","volume":"36","author":"Bodlaender Hans L.","year":"1988","unstructured":"Hans L. Bodlaender. 1988. Some classes of graphs with bounded treewidth. Bulletin of the EATCS 36 (1988), 116\u2013125.","journal-title":"Bulletin of the EATCS"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/1541885.1541892"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/2629654"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/2432622.2432628"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1042"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/1921659.1921664"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.5555\/1283383.1283519"},{"key":"e_1_3_2_14_2","volume-title":"26th Annual European Symposium on Algorithms, ESA","author":"Chitnis Rajesh","year":"2018","unstructured":"Rajesh Chitnis, Andreas Emil Feldmann, and Pasin Manurangsi. 2018. Parameterized approximation algorithms for bidirected Steiner network problems. In 26th Annual European Symposium on Algorithms, ESA. 20:1\u201320:16."},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-13524-3_14"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1137\/18M122371X"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/2601070"},{"key":"e_1_3_2_19_2","series-title":"Graduate Texts in Mathematics","volume-title":"Graph Theory (3rd ed.)","author":"Diestel Reinhard","year":"2005","unstructured":"Reinhard Diestel. 2005. Graph Theory (3rd ed.). Graduate Texts in Mathematics, Vol. 173. Springer-Verlag, Berlin. xvi+411 pages."},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010302"},{"key":"e_1_3_2_22_2","volume-title":"STACS","author":"Eiben Eduard","year":"2019","unstructured":"Eduard Eiben, Dusan Knop, Fahad Panolan, and Ondrej Such\u00fd. 2019. Complexity of the Steiner network problem with respect to the number of terminals. In STACS. 25:1\u201325:17."},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704441241"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2016.27"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.09.065"},{"key":"e_1_3_2_26_2","volume-title":"Parameterized Complexity Theory","author":"Flum J\u00f6rg","year":"2006","unstructured":"J\u00f6rg Flum and Martin Grohe. 2006. Parameterized Complexity Theory. Springer."},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-1324-4"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2008.06.004"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1137\/100794560"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1029"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9630-x"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.5555\/314500.314909"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480101393155"},{"key":"e_1_3_2_35_2","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1007\/978-3-662-53536-3_22","volume-title":"International Workshop on Graph-Theoretic Concepts in Computer Science (WG)","author":"Such\u00fd Ond\u0159ej","year":"2016","unstructured":"Ond\u0159ej Such\u00fd. 2016. On directed Steiner trees with multiple roots. In International Workshop on Graph-Theoretic Concepts in Computer Science (WG). 257\u2013268."},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523690"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3580376","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3580376","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:37:42Z","timestamp":1750178262000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3580376"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,12]]},"references-count":35,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2023,12,31]]}},"alternative-id":["10.1145\/3580376"],"URL":"https:\/\/doi.org\/10.1145\/3580376","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2023,12,12]]},"assertion":[{"value":"2020-09-15","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-01-12","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-12-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}