无向图中边不相交Min-Min问题的复杂度

摘要

We show incorrectness of the NP-completeness proof of Bhatia et al.for the edge-disjoint Min-Min problem in undirected graphs,by giving a counter example that is an unsatisfiable 3SAT instance but was classified satisfiable in the proof of Bhatia etal. We then give a proof of NP-completeness of the edge-disjoint Min-Min problem in undirected graphs,based on a reduction from the MAX-2SAT problem.%Bhatia等指出,Xu等对无向图中的边不相交Min-Min问题的NP-完全性证明并不成立.我们首先用一个反例指出Bhatia等对Xu等的NP-完全性证明的修正依然存在错误.基于一个从MAX-2SAT的归约,我们给出了一个无向图中边不相交Min-Min问题的NP-完全性的正确证明.