Hardness of finding two edge-disjoint Min-Min paths in digraphs

The Min-Min problem of finding a disjoint path pair with the length of the shorter path minimized is known to be NP-complete and no K-approximation exists for any K ≥ 1 [1]. In this paper, we give a simpler proof of this result in general digraphs. We show that this proof can be extended to the problem in planar digraphs whose complexity was unknown previously. As a by-product, we show this problem remains NP-complete even when all edge costs are equal (i.e. strongly NP-complete).Longkun Guo and Hong She