@inproceedings{a9a675f97d0c4af4b2994821d3fbc977,
title = "On the complexity of the edge-disjoint min-min problem in undirected graphs",
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 admits no K-approximation for any K > 1 in the general case [1]. In this paper, we show that Bhatia et al [2]'s NP-complete proof, a claim of correction to Xu et al's proof [1], for the edge-disjoint min-min problem in undirected graphs is incorrect by giving a counter example that is an unsatisfiable 3SAT instance but classified as a satisfiable 3SAT instance in Bhatia et al's proof [2]. We then give a correct proof of NP-completeness of this problem in undirected graphs.",
keywords = "MAX-2SAT, Min-min problem, NP-completeness, disjoint path pair, strongly NP-completeness",
author = "Longkun Guo and Hong Shen",
year = "2011",
doi = "10.1109/ICCRD.2011.5764102",
language = "English",
isbn = "9781612848372",
series = "ICCRD2011 - 2011 3rd International Conference on Computer Research and Development",
pages = "150--154",
booktitle = "ICCRD2011 - 2011 3rd International Conference on Computer Research and Development",
note = "2011 3rd International Conference on Computer Research and Development, ICCRD 2011 ; Conference date: 11-03-2011 Through 15-03-2011",
}