Next: MINIMUM CLIQUE PARTITION Up: Covering and Partitioning Previous: MAXIMUM H-MATCHING Index

### MINIMUM BOTTLENECK PATH MATCHING

- 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 [125].