Marx, Dániel
The Complexity Landscape of FixedParameter Directed Steiner Network Problems (Invited Talk)
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 minimumcost 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 polynomialtime 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 fixedparameter 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 fixedparameter 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.
BibTeX  Entry
@InProceedings{marx:LIPIcs:2016:6053,
author = {D{\'a}niel Marx},
title = {{The Complexity Landscape of FixedParameter Directed Steiner Network Problems (Invited Talk)}},
booktitle = {15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
pages = {32:132:1},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770118},
ISSN = {18688969},
year = {2016},
volume = {53},
editor = {Rasmus Pagh},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6053},
URN = {urn:nbn:de:0030drops60535},
doi = {10.4230/LIPIcs.SWAT.2016.32},
annote = {Keywords: Directed Steiner Tree, Directed Steiner Network, fixedparameter tractability, dichotomy}
}
22.06.2016
Keywords: 

Directed Steiner Tree, Directed Steiner Network, fixedparameter tractability, dichotomy 
Seminar: 

15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)

Issue date: 

2016 
Date of publication: 

22.06.2016 