- INSTANCE:
A directed graph
, an edge cost function
, a collection
of ordered node pairs, and an integer
.
- SOLUTION: A subgraph of that containes an shortest path for (at least) k pairs .
- COST FUNCTION: .
- OBJECTIVE:
Mininimize.
*Approx.:*Approximable within for every [10].*Hardness:*NP-hard to approximate within .*Comment:*The k-Directed Steiner Forest (k-DSF) is approximable within for every [47].

2015-04-27 Revision: 288 PDF version