On the complexity of the edge-disjoint min–min problem in planar 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 (Xu et al., 2006) [1]. In this paper, we prove that in planar digraphs the edge-disjoint min–min problem remains NP-complete and admits no K-approximation for any K>1 unless P=NP. As a by-product, we show that this problem remains NP-complete even when all edge costs are equal (i.e., stronglyNP-complete). To our knowledge, this is the first NP-completeness proof for the edge-disjoint min–min problem in planar digraphs.