On Finding Min-Min Disjoint Paths
The Min-Min problem of finding a disjoint-path pair with the length of the shorter path minimized is known to be NP-hard and admits no K-approximation for any K>1 in the general case (Xu et al. in IEEE/ACM Trans. Netw. 14:147158, 2006).
disjoint paths min-min problem np-hardness planar graph polynomial-time algorithm shortest path