- INSTANCE: Graph with an even number of vertices, and a weight function .
- SOLUTION:
A disjoint path perfect matching for
*G*, i.e., a collection of disjoint simple paths in*G*with disjoint end points. - MEASURE:
Weight of the heaviest path in the matching, i.e.,
.

*Good News:*Approximable within 2 [135].