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

Longkun Guo; Hong Shen

doi:10.1016/j.tcs.2011.12.009

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

Longkun Guo, Hong Shen

Research output: Contribution to journal › Article › peer-review

7 Citations (Scopus)

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.

Original language	English
Pages (from-to)	58-63
Number of pages	6
Journal	Theoretical Computer Science
Volume	432
DOIs	https://doi.org/10.1016/j.tcs.2011.12.009
Publication status	Published - 11 May 2012
Externally published	Yes

Keywords

Disjoint path
Inapproximability
Min-min problem
NP-complete
Planar digraph

Access to Document

10.1016/j.tcs.2011.12.009

Cite this

@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: [email protected] (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 BV",

}

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 - https://www.scopus.com/pages/publications/84859527092

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 -

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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this