TY - JOUR

T1 - On the complexity of the edge-disjoint min-min problem in planar digraphs

AU - Guo, Longkun

AU - Shen, Hong

N1 - Funding Information:
✩ This work was partially supported by the ‘‘100 Talents’’ Project of Chinese Academy of China, National Science Foundation of China grant #61170232 and∗ Correspondingauthorat:SchoolofComputerandInformationTechnology,BeijingJiaotongUniversity,China.Tel.:+61883035592.FundamentalResearchFundsfortheCentralUniversities.ThecorrespondingauthorisHongShen. E-mail address: [email protected] (H. Shen).

PY - 2012/5/11

Y1 - 2012/5/11

N2 - 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.

AB - 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.

KW - Disjoint path

KW - Inapproximability

KW - Min-min problem

KW - NP-complete

KW - Planar digraph

UR - http://www.scopus.com/inward/record.url?scp=84859527092&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2011.12.009

DO - 10.1016/j.tcs.2011.12.009

M3 - Article

AN - SCOPUS:84859527092

SN - 0304-3975

VL - 432

SP - 58

EP - 63

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -