Parameterized Complexity of Arc-Weighted Directed Steiner Problems

Ondra Suchý

Abstract

(joint work with J. Guo and R. Niedermeier)

In Steiner-type problems, generally the task is to find in a given weighted graph a low-cost subgraph connecting the given set of terminals. In the directed case this could mean connecting the given root to all the other terminals (Directed Steiner Tree) connect every terminal to each other (Strongly Connected Steiner Sub-graph) or just connect the prescribed pairs in the prescribed direction (Directed Steiner Network). These problems are generally NP-hard and there are numerous results on polynomial-time approximability.

We initiate a systematic parameterized complexity study of these three fundamental network design problems on arc-weighted directed graphs. We investigate their parameterized complexities with respect to the parameters "number of terminals","an upper bound on the size of the connecting network",