- INSTANCE:
Multigraph
,
collection of vertex pairs
.
- SOLUTION:
A collection of edge disjoint paths in
*G*connecting some of the pairs , i.e. sequences of vertices such that, for some*i*, , , and for any*j*, . - MEASURE:
The number of vertex pairs
that are connected by the paths.

*Good News:*Approximable within [447].*Bad News:*Not approximable within for any unless NPQP [366].*Comment:*Similar to MINIMUM UNSPLITTABLE FLOW. Approximable within for constant degree graphs and butterfly graphs [447]. Approximable within 2 if*G*is a tree with parallel edges. Approximable within if*G*is a two-dimensional mesh [43], or more generally, if*G*is a nearly-Eulerian uniformly high-diameter planar graph [324].Variation in which the objective is to minimize the number of rounds that together connect all pairs, is approximable within on general multigraphs and within on butterfly graphs [447].

MINIMUM PATH COLORING is the variation in which each path is assigned a color, where only paths with the same color need to be edge disjoint, and where the objective is to minimize the number of colors that are needed to connect all vertex pairs in the input. This problem is approximable within 3/2 on trees, within 2 on cycles [415], within on two-dimensional meshes [412], and within on nearly-Eulerian uniformly high-diameter planar graphs [324].

*Garey and Johnson:*Similar to ND40