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 -