Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Feldmann, Andreas Emil; Marx, Dániel http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-63060
URL:

;

The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems

pdf-format:


Abstract

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. 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, while 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. 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 H is a class of directed graphs, then we look at the special case of Directed Steiner Network where the list (s_1, t_1), ..., (s_k, t_k) of requests form a directed graph that is a member of H. Our main result is a complete characterization of the classes H resulting in fixed-parameter tractable special cases: we show that if every pattern in H has the combinatorial property of being "transitively equivalent to a bounded-length caterpillar with a bounded number of extra edges," then the problem is FPT, and it is W[1]-hard for every recursively enumerable H not having this property. This complete dichotomy unifies and generalizes the known results showing that Directed Steiner Tree is FPT [Dreyfus and Wagner, Networks 1971], Strongly Connected Steiner Subgraph is W[1]-hard [Guo et al., SIAM J. Discrete Math. 2011], and Directed Steiner Network is solvable in polynomial-time for constant number of terminals [Feldman and Ruhl, SIAM J. Comput. 2006], and moreover reveals a large continent of tractable cases that were not known before.

BibTeX - Entry

@InProceedings{feldmann_et_al:LIPIcs:2016:6306,
  author =	{Andreas Emil Feldmann and D{\'a}niel Marx},
  title =	{{The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{27:1--27:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6306},
  URN =		{urn:nbn:de:0030-drops-63060},
  doi =		{10.4230/LIPIcs.ICALP.2016.27},
  annote =	{Keywords: Directed Steiner Tree, Directed Steiner Network, fixed-parameter tractability, dichotomy}
}

Keywords: Directed Steiner Tree, Directed Steiner Network, fixed-parameter tractability, dichotomy
Seminar: 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Issue date: 2016
Date of publication: 2016


DROPS-Home | Fulltext Search | Imprint Published by LZI