Four-point conditions for the TSP : the complete complexity classification

V.G. Deineko, B. Klinz, A. Tiskin, G.J. Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

7 Citations (Scopus)
2 Downloads (Pure)

Abstract

The combinatorial optimization literature contains a multitude of polynomially solvable special cases of the traveling salesman problem (TSP) which result from imposing certain combinatorial restrictions on the underlying distance matrices. Many of these special cases have the form of so-called four-point conditions: inequalities that involve the distances between four arbitrary cities. In this paper we classify all possible four-point conditions for the TSP with respect to computational complexity, and we determine for each of them whether the resulting special case of the TSP can be solved in polynomial time or whether it remains NP-hard. Keywords: Traveling salesman problem; Four-point condition; Polynomially solvable case
Original languageEnglish
Pages (from-to)147-159
JournalDiscrete Optimization
Volume14
DOIs
Publication statusPublished - 2014

Fingerprint Dive into the research topics of 'Four-point conditions for the TSP : the complete complexity classification'. Together they form a unique fingerprint.

Cite this