- INSTANCE:
A tree
,
a capacity function
and
*k*pairs of vertices . - SOLUTION:
A flow
for each pair
with
such that, for each
,
where
if
*e*belongs to the unique path from and , 0 otherwise. - MEASURE:
The sum of the flows, i.e.,
.

*Good News:*Approximable within 2 [190].*Bad News:*APX-complete [190].*Comment:*Transformation from MAXIMUM 3-DIMENSIONAL MATCHING. It remains APX-complete even if the edge capacities are 1 and 2.