Parameterized Complexity of Arc-Weighted Directed Steiner Problems

Abstract

We initiate a systematic parameterized complexity study of three fundamental network design problems on arc-weighted directed graphs: Directed Steiner Tree, Strongly Connected Steiner Subgraph and Directed Steiner Network. We investigate their parameterized complexities with respect to the parameters "number of terminals", "an upper bound on the size of the connecting network", and the combination of both.

We achieve several parameterized hardness as well as some fixed-parameter tractability results, in this way significantly extending previous results of Feldman and Ruhl [SIAM J. Comp. 2006].

Keywords

• computational intractability
• W[1]- and W[2]-hardness
• fixed-parameter tractability
• problem kernel
• graph algorithm
• network design