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

详细信息	查看全文 | 推荐本文 |

• 作者：Longkun Guo^a ; Hong Shen^b ; ^c ; ^{hong@cs.adelaide.edu.au}
• 关键词：Min&ndash ; min problem ; Planar digraph ; NP-complete ; Disjoint path ; Inapproximability
• 刊名：Theoretical Computer Science
• 出版年：2012
• 期刊代码：114_03043975
• 类别：cp
• 出版时间：11 May, 2012
• 卷：432
• 期：Complete
• 页码：58-63
• 文件大小：341 K

摘要

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) . In this paper, we prove that in planar digraphs the edge-disjoint min-min problem remains NP-complete and admits no -approximation for any unless . 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.