The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals
Authors:
- Jon FeldmanJFJon Feldman
- Matthias RuhlMRMatthias Ruhl
- 1 January 2006
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 36 (2) , 543-561
Abstract
We consider the Directed Steiner Network problem, also called the Point‐to‐Point Connection problem. Given a directed graph G and p pairs $\{ (s_1,t_1), \dotsc, (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 \geq 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.
Keywords
This publication has 13 references indexed in Scilit:
- The point-to-point connection problem — analysis and algorithmsDiscrete Applied Mathematics, 1997
- Multicast tree generation in networks with asymmetric linksIEEE/ACM Transactions on Networking, 1996
- On the point-to-point connection problemInformation Processing Letters, 1995
- The point-to-point delivery and connection problems: complexity and algorithmsDiscrete Applied Mathematics, 1992
- Routing in Point-to-Point Delivery Systems: Formulations and Solution HeuristicsTransportation Science, 1990
- Faster algorithms for the shortest path problemJournal of the ACM, 1990
- Fibonacci heaps and their uses in improved network optimization algorithmsJournal of the ACM, 1987
- Network Design and Transportation Planning: Models and AlgorithmsTransportation Science, 1984
- Steiner's problem in graphs and its implicationsNetworks, 1971
- The steiner problem in graphsNetworks, 1971