On the Complexity of the Edge-Disjoint Min-Min Problem in Undirected Graphs
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 2s NP-complete proof, a claim of correction to Xu et als 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 als proof 2. We then give a correct proof of NP-completeness of this problem in undirected graphs.
Min-min problem NP-completeness strongly NP-completeness disjoint path pair MAX-2SAT
Longkun Guo Hong Shen
School of Computer Science, University of Science and Technology of China, China School of Computer Science, University of Science and Technology of China, China SchooI of Computer
国际会议
上海
英文
150-154
2011-03-11（万方平台首次上网日期，不代表论文的发表时间）