article

Free access

The traveling salesman problem in graphs with 3-edge cutsets

Authors:

G. Cornuéjols,

W. PulleyblankAuthors Info & Claims

Journal of the ACM (JACM), Volume 32, Issue 2

Pages 383 - 410

https://doi.org/10.1145/3149.3154

Published: 01 April 1985 Publication History

Abstract

This paper analyzes decomposition properties of a graph that, when they occur, permit a polynomial solution of the traveling salesman problem and a description of the traveling salesman polytope by a system of linear equalities and inequalities. The central notion is that of a 3-edge cutset, namely, a set of 3 edges that, when removed, disconnects the graph. Conversely, our approach can be used to construct classes of graphs for which there exists a polynomial algorithm for the traveling salesman problem. The approach is illustrated on two examples, Halin graphs and prismatic graphs.

References

[1]

BACHEM, A., AND GROTSCHEL, M.maticsmOptimization and Operations Research, B. Korte, Ed. North Holland, Amsterdam, 1982, pp. 51-106.

[2]

BOULALA, M., AND UHRY, J. P.Polytope des ind6pendants d'un graphe s6rie-parall61e. Discrete Math. 27 (1979), 225-243.

[3]

CORNU~OLS, G., NADDEF, D., AND PULLEYBLANK, W. Halin graphs and the travelling salesman problem. Math. Prog. 16 (1983), 287-294.

[4]

CORNUEJOLS, G., AND PULLEYBLANK, W. The travelling salesman polytope and {0, 2}-matchings. Ann. Discrete Math. 16 (1982), 27-55.

[5]

CROWDER, H., AND PADBERG, M. W. Solving large-scale symmetric travelling salesman problems to optimality. Manage. Sci. 26 (1980), 495-509.

[6]

CUTLER, Efficient special case algorithm for the N line planar travelling salesman problem. Networks 10 (1980), 183-195.

[7]

EDMONDS, J. Maximum matching and a polyhedron with 0, 1 vertices. J. Res. Nat. Bur. Standards 69B (1965), 125-130.

[8]

EDMONDS, J.Matroid intersection. Ann. Disc. Math. 4 (1979), 39-49.

[9]

GARFINKEL, R. S.Minimizing wallpaper waste. Part I: A class of travelling salesman problems. Oper. Res. 25 (1977), 741-751.

[10]

GILES, F. R., AND TROTTER, L. E.On stable set polyhedra for Kt,3-free graphs. J. Comb. Theory Series B 31 (1981), 313-326.

[11]

GILMORE, P. C., AND GOMORY, R. E.Sequencing a one state-variable machine: A solvable case of the travelling salesman problem. Oper. Res. 12 (1964), 655-679.

[12]

GROTSCHEL, M.On the monotone symmetric travelling salesman problem: Hypohamiltonian/ hypotraceable graphs and facets. Math. Oper. Res. 5 (1980), 285-292.

[13]

GROTSCHEL, M. Polyedrische Characterisierungen kombinatorischen Optimierungsprobleme. Verlag Anton Hain, Meisenheim am Glan, Germany, 1977.

[14]

GROTSCHEL, M., Lov~,sz, L., AND SCHRIJVER, A.The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1 ( 198 l), 169-197.

[15]

GROTSCHEL, M., AND PADBERG, M. W. On the symmetric travelling salesman problem I and II. Math. Prog. 16 (1979), 265-302.

[16]

GROTSCHEL, M., AND PADBERG, M. W. Polyhedral aspects of the traveling salesman problem i: Theory. To be published in The Traveling Salesman Problem, E. L. Lawler, J. K. Lenstra, and A. H. G. Rinnooy Kan, Eds. Wiley, New York.

[17]

GROTSCHEL, M., AND PADBERG, M. W. Polyhedral aspects of the traveling salesman problem II: Computation. To be published in The Traveling Salesman Problem, E. L. Lawler, J. K. Lenstra, and A. H. G. Rinnooy Kan, Eds. Wiley, New York.

[18]

GROTSCHEL, M., AND PULLEYBLANK, W.Clique tree inequalities and the symmetric travelling salesman problem. Report 81196-OR, Institut fiir Okonometrie und Operations Research, Bonn, Germany, 1981 (Math. Oper. Res., to be published).

[19]

HALIN, R.Studies on minimally n-connected graphs. Combinatorial Mathematics and Its Applications, D. J. A. Welsh, Ed. Academic Press, New York, 1971, pp. 129-136.

[20]

HELD, M., AND KARP, R.The travelling salesman problem and minimum spanning trees, Part I. Oper. Res. 18 (1970), 1138-1162.

[21]

HELD, M., AND KARP, R.The travelling salesman problem and minimum spanning trees, Part II. Math. Prog. 1 (1971), 6-25.

[22]

LAWLER, E. A solvable case of the travelling salesman problems. Math. Prog. i (1971), 267-269.

[23]

LITTLE, G., MURTY, K., SWEYNEY, D., AND KAREL, C.An algorithm for the travelling salesman problem. Oper. Res. 11 (1963), 972-989.

[24]

LovAsz, L., AND PLUMMER, M.On a family of planar bicritical graphs. Proc. London Math. Soc. 30(1975), 160-176.

[25]

MINTY, G.On maximal independent sets of vertices in claw-free graphs. J. Comb. Theory Series B 28 (1980), 284-304.

[26]

NADDEF, D., AND PULLEYBLANK, W.Ear decomposition of elementary graphs and GF2-rank of perfect matchings. Ann. Discrete Math. 16 (1982), 241-260.

[27]

PULLEYBLANK, W.The matching rank of Halin graphs. Rapport de Recherche 210 IMAG, Universit6 Scientifique et M6dicale de Grenoble, Grenoble, France, 1980.

[28]

RATLIFF, H. D., AND ROSENTHAL, A. S.Order-picking in a rectangular warehouse. A solvable case of the travelling salesman problem. Op. Res. 31 (1983), 507-521.

[29]

SBIHI, N.Algorithme de recherche d'un stable de cardinalit~ maximum dans un graphe sans 6toile. Discrete Math. 29 (1980), 53-76.

[30]

SYSLO, M. A new solvable case of the travelling salesman problem. Math. Prog. 4 (1973), 347- 348.

[31]

SYSLO, M., AND PROSKUROWSKI, A. On Halin graphs. In Graph Theory Lag6w 1981. Lecture Notes in Mathematics, vol. 1018. Springer-Vedag, Berlin-Heidelberg, 1981, pp. 248-256.

Cited By

Haddadan ANewman A(2022)Towards improving Christofides algorithm on fundamental classes by gluing convex combinations of toursMathematical Programming: Series A and B10.1007/s10107-022-01784-w198:1(595-620)Online publication date: 21-Mar-2022
https://dl.acm.org/doi/10.1007/s10107-022-01784-w
Baïou MBarahona F(2018)Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problemMathematical Programming: Series A and B10.5555/3288898.3288957172:1-2(59-75)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.5555/3288898.3288957
Baïou MBarahona F(2018)Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problemMathematical Programming10.1007/s10107-017-1227-3172:1-2(59-75)Online publication date: 27-Jan-2018
https://doi.org/10.1007/s10107-017-1227-3
Show More Cited By

Index Terms

The traveling salesman problem in graphs with 3-edge cutsets
1. Mathematics of computing
  1. Discrete mathematics
  2. Mathematical analysis
    1. Mathematical optimization
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization

Recommendations

Halin graphs and the travelling salesman problem

A Halin graphH=TźC is obtained by embedding a treeT having no nodes of degree 2 in the plane, and then adding a cycleC to join the leaves ofT in such a way that the resulting graph is planar. These graphs are edge minimal 3-connected, hamiltonian, and ...
On 3-Edge-Connected Supereulerian Graphs

The supereulerian graph problem, raised by Boesch et al. (J Graph Theory 1:79–84, 1977), asks when a graph has a spanning eulerian subgraph. Pulleyblank showed that such a decision problem, even when restricted to planar graphs, is NP-complete. Jaeger ...
On stable cutsets in claw-free graphs and planar graphs

A stable cutset in a connected graph is a stable set whose deletion disconnects the graph. Let K"4 and K"1","3 (claw) denote the complete (bipartite) graph on 4 and 1+3 vertices. It is NP-complete to decide whether a line graph (hence a claw-free graph) ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 32, Issue 2

April 1985

254 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/3149

Issue’s Table of Contents

Copyright © 1985 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 1985

Published in JACM Volume 32, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

28
Total Citations
View Citations
1,215
Total Downloads

Downloads (Last 12 months)76
Downloads (Last 6 weeks)13

Reflects downloads up to 22 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Haddadan ANewman A(2022)Towards improving Christofides algorithm on fundamental classes by gluing convex combinations of toursMathematical Programming: Series A and B10.1007/s10107-022-01784-w198:1(595-620)Online publication date: 21-Mar-2022
https://dl.acm.org/doi/10.1007/s10107-022-01784-w
Baïou MBarahona F(2018)Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problemMathematical Programming: Series A and B10.5555/3288898.3288957172:1-2(59-75)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.5555/3288898.3288957
Baïou MBarahona F(2018)Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problemMathematical Programming10.1007/s10107-017-1227-3172:1-2(59-75)Online publication date: 27-Jan-2018
https://doi.org/10.1007/s10107-017-1227-3
Chen GEnomoto HOzeki KTsuchiya S(2017)Plane Triangulations Without a Spanning Halin Subgraph IISIAM Journal on Discrete Mathematics10.1137/16M107269331:4(2429-2439)Online publication date: Jan-2017
https://doi.org/10.1137/16M1072693
Woods BPunnen AStephen T(2017) A linear time algorithm for the -neighbour Travelling Salesman Problem on a Halin graph and extensions Discrete Optimization10.1016/j.disopt.2017.08.00526(163-182)Online publication date: Nov-2017
https://doi.org/10.1016/j.disopt.2017.08.005
Aziz HCahan CGretton CKilby PMattei NWalsh T(2016)A study of proxies for Shapley allocations of transport costsJournal of Artificial Intelligence Research10.5555/3013589.301360556:1(573-611)Online publication date: 1-May-2016
https://dl.acm.org/doi/10.5555/3013589.3013605
Xia YZhu MGu QZhang LLi X(2016)Toward solving the Steiner travelling salesman problem on urban road maps using the branch decomposition of graphsInformation Sciences: an International Journal10.1016/j.ins.2016.09.043374:C(164-178)Online publication date: 20-Dec-2016
https://dl.acm.org/doi/10.1016/j.ins.2016.09.043
Conforti MPashkovich K(2016)The projected faces property and polyhedral relationsMathematical Programming: Series A and B10.1007/s10107-015-0882-5156:1-2(331-342)Online publication date: 1-Mar-2016
https://dl.acm.org/doi/10.1007/s10107-015-0882-5
Baïou MBarahona F(2016)Sparsest Cut in Planar Graphs, Maximum Concurrent Flows and Their Connections withźthe Max-Cut ProblemProceedings of the 18th International Conference on Integer Programming and Combinatorial Optimization - Volume 968210.1007/978-3-319-33461-5_6(63-76)Online publication date: 1-Jun-2016
https://dl.acm.org/doi/10.1007/978-3-319-33461-5_6
Boyd SIwata STakazawa K(2013)Finding 2-Factors Closer to TSP Tours in Cubic GraphsSIAM Journal on Discrete Mathematics10.1137/11084351427:2(918-939)Online publication date: Jan-2013
https://doi.org/10.1137/110843514
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents