Next: MINIMUM SINGLE-SINK EDGE INSTALLATION
Up: Flow Problems
Previous: MAXIMUM DISJOINT CONNECTING PATHS
  Index
- INSTANCE:
Graph
,
length function
,
and a
pair of vertices s,t in V.
- SOLUTION:
Two vertex disjoint paths in G connecting s and t, i.e. two
sequences of vertices
and
such that
,
,
,
,
and
are included in E,
and for any i,
and
are included in E.
- MEASURE:
The longest of the two paths, i.e.
.
- Good News:
Approximable within 2 [354].
- Comment:
Approximable within 2 also if the paths should be edge disjoint
instead of vertex disjoint.
Variation in which the graph is directed and we look for two vertex (edge)
disjoint directed paths is also approximable within 2, and is not
approximable within
for any
[354].
- Garey and Johnson: Similar to ND41
Viggo Kann
2000-03-20