Hardness of the edge-disjoint Min-Min problem in undirected graphs

doi:10.7523/j.issn.2095-6134.2012.4.018

›› 2012, Vol. 29 ›› Issue (4): 549-554.DOI: 10.7523/j.issn.2095-6134.2012.4.018

Previous Articles Next Articles

Hardness of the edge-disjoint Min-Min problem in undirected graphs

GUO Long-Kun, SHEN Hong

School of Computer Science, University of Science and Technology of China, Hefei 230026, China

Received:2011-04-02 Revised:2011-05-20 Online:2012-07-15

Abstract

Abstract: 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.

Key words: Min-Min problem, NP-completeness, disjoint path pair, MAX-2SAT

CLC Number:

TP301.5

GUO Long-Kun, SHEN Hong. Hardness of the edge-disjoint Min-Min problem in undirected graphs[J]. , 2012, 29(4): 549-554.

References

[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.

Hardness of the edge-disjoint Min-Min problem in undirected graphs

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 1

Recommended Articles

Metrics

Comments