2026-07-22T11:56:49Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6053 2024-03-06T10:37:32Z ddc:004 open_access

The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems (Invited Talk) Marx, Dániel Directed Steiner Tree Directed Steiner Network fixed-parameter tractability dichotomy Given a directed graph G and a list (s_1,t_1), ..., (s_k,t_k) of terminal pairs, the Directed Steiner Network problem asks for a minimum-cost subgraph of G that contains a directed s_i-> t_i path for every 1<= i <= k. Feldman and Ruhl presented an n^{O(k)} time algorithm for the problem, which shows that it is polynomial-time solvable for every fixed number k of demands. There are special cases of the problem that can be solved much more efficiently: for example, the special case Directed Steiner Tree (when we ask for paths from a root r to terminals t_1, ..., t_k) is known to be fixed-parameter tractable parameterized by the number of terminals, that is, algorithms with running time of the form f(k)*n^{O(1)} exist for the problem. On the other hand, the special case Strongly Connected Steiner Subgraph (when we ask for a path from every t_i to every other t_j) is known to be W[1]-hard parameterized by the number of terminals, hence it is unlikely to be fixed-parameter tractable. In the talk, we survey results on parameterized algorithms for special cases of Directed Steiner Network, including a recent complete classification result (joint work with Andreas Feldmann) that systematically explores the complexity landscape of directed Steiner problems to fully understand which special cases are FPT or W[1]-hard. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dániel Marx 2016 Is Part Of LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2016.32 urn:nbn:de:0030-drops-60535 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.32 eng https://creativecommons.org/licenses/by/3.0/legalcode