** Next:** Directed Steiner Forest (DSF)
** Up:** Steiner Forest Problems
** Previous:** Degree Bounded Survivable Network

- INSTANCE:
A directed graph
, edge weights
, set of terminals
- SOLUTION:
A set of edges
such that for all
the induced subgraph
contains a directed
-path
- COST FUNCTION:
- OBJECTIVE:
Minimize.
*Approx.:*
Approximable within
for every
[27].
*Hardness:*
For every fixed
, the SCSS cannot be approximated within ratio
, unless
[61].
*Comment:*
In a variant
-SCSS
, the number of terminals is
, and the task is to construct a subset
such that
contains
-paths
and
-paths. The objective is to minimize
, where
is the maximum number of
-paths or
-paths using edge
.
The
-SCSS
can be solved in
time but does not have an
algorithm for any computable function
, unless
the Exponential Time Hypothesis (ETH) fails [35].

** Next:** Directed Steiner Forest (DSF)
** Up:** Steiner Forest Problems
** Previous:** Degree Bounded Survivable Network
2015-04-27 Revision: 288 PDF version