The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems (Invited Talk)

Author Dániel Marx



PDF
Thumbnail PDF

File

LIPIcs.SWAT.2016.32.pdf
  • Filesize: 239 kB
  • 1 pages

Document Identifiers

Author Details

Dániel Marx

Cite AsGet BibTex

Dániel Marx. The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems (Invited Talk). In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, p. 32:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.SWAT.2016.32

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. 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.
Keywords
  • Directed Steiner Tree
  • Directed Steiner Network
  • fixed-parameter tractability
  • dichotomy

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail