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., strongly NP-complete). To our knowledge, this is the first NP-completeness proof for the edge-disjoint min-min problem in planar digraphs. (C) 2012 Published by Elsevier B.V.
min-min problem planar digraph disjoint path np-complete inapproximability