MINIMUM BOTTLENECK PATH MATCHING

• INSTANCE: Graph $G=\left(V,E\right)$ with an even number of vertices, and a weight function $w : E \rightarrow N$.
• SOLUTION: A disjoint path perfect matching for G, i.e., a collection $P_1,P_2,\ldots,P_{\vert V\vert/2}$ of disjoint simple paths in G with disjoint end points.
• MEASURE: Weight of the heaviest path in the matching, i.e., $\max\limits_{1\le i\le \vert V\vert/2}\sum\limits_{e\in P_i} w(e)$.

  
  

• Good News: Approximable within 2 [135].