@inproceedings{e5d169c043f84ed8bb8929937308ce84,
title = "Hardness of finding two edge-disjoint Min-Min paths in 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 and no K-approximation exists for any K ≥ 1 [1]. In this paper, we give a simpler proof of this result in general digraphs. We show that this proof can be extended to the problem in planar digraphs whose complexity was unknown previously. As a by-product, we show this problem remains NP-complete even when all edge costs are equal (i.e. strongly NP-complete).",
keywords = "Min-Min problem, NP-completeness, disjoint path, inapproximability, planar digraph",
author = "Longkun Guo and Hong Shen",
note = "Funding Information: This project was partially supported by the “100 Talents” Project of Chinese Academy of China and NSFC grant \#622307. The corresponding author is Hong Shen.; 5th International Frontiers in Algorithmics Workshop and the 7th International Conference on Algorithmic Aspects in Information and Management, FAW-AAIM 2011 ; Conference date: 28-05-2011 Through 31-05-2011",
year = "2011",
doi = "10.1007/978-3-642-21204-8\_32",
language = "English",
isbn = "9783642212031",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "300--307",
booktitle = "Frontiers in Algorithmics and Algorithmic Aspects in Information and Management - Joint International Conference, FAW-AAIM 2011, Proceedings",
}