##
The Directed Steiner Network problem is tractable for a constant number of terminals

**
Jon Feldman and Matthias Ruhl
**
*IEEE Symposium on Foundations of Computer Science (FOCS '99)*

New York, October 1999

[Postscript, 227KB]

[PDF, 170KB]

### Abstract

We consider the Directed Steiner Network problem, also called
the Point-to-Point Connection problem, where given a directed
graph G and p pairs { (s_{1},t_{1}), ...,
(s_{p},t_{p}) } of nodes in the
graph, one has to find the smallest subgraph H of G that contains
paths from s_{i} to t_{i} for all i. The problem is
NP-hard for general p,
since the Directed Steiner Tree problem is a special
case. Until now, the complexity was unknown for constant p >= 3.

We prove that the problem is polynomially solvable if p is any
constant number, even if nodes and edges in G are weighted and the
goal is to minimize the total weight of the subgraph H.

In addition, we give an efficient algorithm for the Strongly Connected
Steiner Subgraph problem for any constant p, where given a directed
graph and p nodes in the graph, one has to compute the smallest
strongly connected subgraph containing the p nodes.

Back to publications