Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Critical graphs, matchings and tours or a hierarchy of relaxations for the travelling salesman problem

  • Published:
Combinatorica Aims and scope Submit manuscript

Abstract

A(perfect) 2-matching in a graphG=(V, E) is an assignment of an integer 0, 1 or 2 to each edge of the graph in such a way that the sum over the edges incident with each node is at most (exactly) two. The incidence vector of a Hamiltonian cycle, if one exists inG, is an example of a perfect 2-matching. Fork satisfying 1≦k≦|V|, we letP k denote the problem of finding a perfect 2-matching ofG such that any cycle in the solution contains more thank edges. We call such a matching aperfect P k -matching. Then fork<l, the problemP k is a relaxation ofP 1. Moreover if |V| is odd, thenP 1V1–2 is simply the problem of determining whether or notG is Hamiltonian. A graph isP k -critical if it has no perfectP k -matching but whenever any node is deleted the resulting graph does have one. Ifk=|V|, then a graphG=(V, E) isP k -critical if and only if it ishypomatchable (the graph has an odd number of nodes and whatever node is deleted the resulting graph has a perfect matching). We prove the following results:

  1. 1.

    If a graph isP k -critical, then it is alsoP l -critical for all largerl. In particular, for allk, P k -critical graphs are hypomatchable.

  2. 2.

    A graphG=(V, E) has a perfectP k -matching if and only if for anyX⊆V the number ofP k -critical components inG[V - X] is not greater than |X|.

  3. 3.

    The problemP k can be solved in polynomial time provided we can recognizeP k -critical graphs in polynomial time. In addition, we describe a procedure for recognizingP k -critical graphs which is polynomial in the size of the graph and exponential ink.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. I. Anderson, Perfect Matchings of a Graph,Journal of Combinatorial Theory B 10 (1971), 183–186.

    Article  Google Scholar 

  2. G. Cornuéjols andW. Pulleyblank, A Matching Problem with Side Conditions,Discrete Mathematics 29 (1980), 135–159.

    Article  MATH  MathSciNet  Google Scholar 

  3. G. Cornuéjols andW. Pulleyblank, Perfect Triangle-Free 2-matchings,Mathematical Programming Study 13 (1980), 1–7.

    MATH  Google Scholar 

  4. G. Cornuéjols andW. Pulleyblank, The Travelling Salesman Polytope and {0,2}-matchings, inAnnals of Discrete Mathematics 16 (1982), 27–55.

    Google Scholar 

  5. J. Edmonds, Paths, Trees and Flowers,Canadian Journal of Mathematics 17 (1965), 449–467.

    MATH  MathSciNet  Google Scholar 

  6. J. Edmonds, Maximum Matching and a Polyhedron with 0,1 Vertices,Journal of Research of the National Bureau of Standards 69 B (1965), 125–130.

    MathSciNet  Google Scholar 

  7. L. Lovász, A Note on Factor-Critical Graphs,Studia Scientiarum Mathematicarum Hungarica 7 (1972), 279–280.

    MathSciNet  Google Scholar 

  8. L. Lovász,Combinatorial Problems and Exercises, North Holland, 1979.

  9. L. Lovász,Private Communication.

  10. W. Pulleyblank,Faces of Matching Polyhedra, Ph. D. Thesis, University of Waterloo (1973).

  11. W. Pulleyblank, Minimum Node Covers and 2-Bicritical Graphs,Mathematical Programming 17 (1979), 91–103.

    Article  MATH  MathSciNet  Google Scholar 

  12. W. Pulleyblank andJ. Edmonds, Facets of 1-matching Polyhedra, inHypergraph Seminar, (eds. C. Berge and D. K. Ray—Chaudhuri), Springer Verlag (1974), 214–242.

  13. W. T. Tutte, The Factorization of Linear Graphs,Journal of the London Mathematical Society 22 (1947), 107–111.

    Article  MATH  MathSciNet  Google Scholar 

  14. W. T. Tutte, The Factors of Graphs,Canadian Journal of Mathematics 4 (1952), 314–328.

    MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. G.S.I.A., Carnegie-Mellon University, 15213, Pittsburgh, PA, USA

    G. Cornuéjols

  2. Department of Combinatorics and Optimization, University of Waterloo, N2L 3G1, Waterloo, Ontario, Canada

    W. R. Pulleyblank

Authors
  1. G. Cornuéjols
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. W. R. Pulleyblank
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Dedicated to Tibor Gallai on his seventieth birthday

Supported by NSF grant ENG 79-02506.

Supported by Sonderforschungsbereich 21 (DFG), Institut für Operations Research, Universität Bonn. and by the National Science and Engineering Research Council of Canada.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Cornuéjols, G., Pulleyblank, W.R. Critical graphs, matchings and tours or a hierarchy of relaxations for the travelling salesman problem. Combinatorica 3, 35–52 (1983). https://doi.org/10.1007/BF02579340

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02579340

AMS subject classification (1980)

Search

Navigation