Bhatia等指出,Xu等对无向图中的边不相交Min-Min问题的NP-完全性证明并不成立. 我们首先用一个反例指出Bhatia等对Xu等的NP-完全性证明的修正依然存在错误. 基于一个从MAX-2SAT的归约,我们给出了一个无向图中边不相交Min-Min问题的NP-完全性的正确证明.
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 et al. 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.
[1] Xu D, Chen Y, Xiong Y, et al. On the complexity of and algorithms for finding the shortest path with a disjoint counterpart[J]. IEEE/ACM Transactions on Networking, 2006, 14(1):147-158.
[2] Bhatia R, Kodialam M, Lakshman T. Finding disjoint paths with related path costs[J]. Journal of Combinatorial Optimization, 2006, 12(1): 83-96.
[3] Bouillet E, Labourdette J, Ramamurthy R, et al. Lightpath re-optimization in mesh optical networks[J]. IEEE/ACM Transactions on Networking (TON), 2005, 13(2): 437-447.
[4] Li C, McCormick S, Simchi-Levi D. Finding disjoint paths with different path-costs: Complexity and algorithms[J]. Networks, 1992, 22(7): 653-667.
[5] Zheng S, Yang B, Yang M, et al. Finding minimum-cost paths with minimum sharability //26th IEEE International Conference on Computer Communications. 2007: 1532-1540.
[6] Seymour P. Disjoint paths in graphs[J]. Discrete Mathematics, 2006, 306(10): 979-991.
[7] Liu G, Ramakrishnan K. A* Prune: an algorithm for finding K shortest paths subject tomultiple constraints //IEEE INFOCOM 2001.Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies. 2001, 2: 743-749.
[8] Shiloach Y. A polynomial solution to the undirected two paths problem[J]. Journal of the ACM (JACM), 1980, 27(3):445-456.
[9] Suurballe J. Disjoint paths in a network[J]. Networks,1974, 4(2): 125-145.
[10] Suurballe J, Tarjan R. A quick method for finding shortest pairs of disjoint paths[J]. Networks, 1984, 14(2): 325-336.
[11] Bhandari R. Optimal physical diversity algorithms and survivable networks //Proceedings of Second IEEE Symposium on Computers and Communications. 1997: 433-441.
[12] Li C, McCormick T, Simich-Lev D. The complexity of finding two disjoint paths with min-max objective function[J]. Discrete Applied Mathematics, 1989, 26(1): 105-115.
[13] Sen A. Survivability of lightwave networks-path lengths in WDM protection scheme[J]. Journal of High Speed Networks, 2001, 10(4): 303-315.
[14] Holst H, Pina J. Length-bounded disjoint paths in planar graphs[J]. Discrete Applied Mathematics, 2002, 120(1): 251-261.
[15] Guo L, Shen H. Hardness of finding two edge-disjoint Min-Min paths in digraphs //Lecture Notes in Computer Science 6681.Springer, 2011: 301-308.
[16] Schrijver A. Finding k disjoint paths in a directed planar graph[J]. SIAM J Computing, 1994, 23(4): 780-788.
[17] Garey M, Johnson L. Some simplified NP-complete graph problems[J]. Theoretical Computer Science, 1976, 1(3): 237-267.
