@article{5d0dbfe2dc42414d919cf19cb94319f3,

title = "On the complexity of the edge-disjoint min-min problem in planar digraphs",

abstract = "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.",

keywords = "Disjoint path, Inapproximability, Min-min problem, NP-complete, Planar digraph",

author = "Longkun Guo and Hong Shen",

note = "Funding Information: ✩ This work was partially supported by the {\textquoteleft}{\textquoteleft}100 Talents{\textquoteright}{\textquoteright} 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: hong@cs.adelaide.edu.au (H. Shen).",

year = "2012",

month = may,

day = "11",

doi = "10.1016/j.tcs.2011.12.009",

language = "English",

volume = "432",

pages = "58--63",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

}