Definition · Hamilton circuit, and the travelling salesmanA Hamilton circuit is a cycle visiting every vertex of a graph exactly once. The travelling salesman decision problem takes a distance for every pair of cities and a budget, and asks whether some tour visiting every city once and returning costs at most the budget.
The construction
for every pair u, v: D[u][v] = 1 if uv is an edge of G
D[u][v] = 2 if it is not
budget B = n, the number of vertices
Theorem · The construction is a reductionThe graph has a Hamilton circuit if and only if the constructed instance has a tour of cost at most n.
A tour visits n cities and returns, so it takes exactly n steps, and every step costs 1 or 2. Its cost is therefore at least n, with equality exactly when every step costs 1, that is, when every step is an edge of G — which makes the tour a Hamilton circuit.
So if a Hamilton circuit exists it is a tour of cost exactly n, which is within budget; and if a tour of cost at most n exists then its cost is exactly n, every step is an edge, and it is a Hamilton circuit. The two lists of solutions are therefore equal as sets of cyclic sequences, which is stronger than the reduction needs.
□
What the lab enumerated
The loaded graph is the five-cycle. The panel reports 5 vertices and 5 edges, a budget of 5, 12 tours considered, 1 tour within budget, 1 Hamilton circuit, the verdict that the two lists are the same list, a shortest tour of 5, and the two answers agreeing. The single tour within budget is the cycle itself.
Twelve is (n − 1)! divided by 2: a tour is counted once rather than twice for itself and its reverse, and it is counted starting from city 1. Getting that convention wrong is a real hazard here, because counting a cycle and its reverse separately would make a bijection look like a two-to-one map, and the panel's verdict on the map would then be wrong for a reason having nothing to do with the construction.
Example · Why the other eleven tours cost moreThe five-cycle has 5 edges out of 10 pairs, so half the distances are 2. Any ordering other than the cycle itself must use at least one non-edge, so it costs at least 6 — and the panel's table shows no tour of 6 at all. The lengths across the twelve are 5, 7, 8 and 10, because dropping one edge of the cycle leaves a path whose ends are joined only by that same edge: using one non-edge forces a second. The budget separates the one from the eleven, and it is the only thing doing the separating.
Composing reductions, and where this one sits
Satisfiability is not reduced to the travelling salesman in one step by anyone. The route runs through a sequence of problems, each link a construction with its own gadget, and composition does the rest: two polynomial maps compose to a polynomial map, and the yes-or-no equivalences compose to a yes-or-no equivalence. This page builds the last link, and the link from independent set to Hamilton circuit is stated here and built nowhere in this library — its gadget needs more vertices than the lab can enumerate over.
That gap is worth being explicit about rather than papering over with an arrow. What has been built in front of you on this course is: search from decision, satisfiability to independent set, the identity carrying independent set to vertex cover and clique, satisfiability to subset sum, and Hamilton circuit to the travelling salesman. What is quoted and not built is Cook–Levin — that satisfiability is NP-complete at all — and the middle of the chain into Hamilton circuits.
Theorem · No constant-factor approximation for the general travelling salesmanIf for some constant ρ ≥ 1 there is a polynomial-time algorithm always returning a tour of cost at most ρ times the optimum, then the Hamilton circuit problem is solvable in polynomial time, and hence P = NP.
B
u
i
l
d
t
h
e
d
i
s
t
a
n
c
e
m
a
t
r
i
x
w
i
t
h
1
o
n
t
h
e
e
d
g
e
s
a
n
d
`
ρ
·
n
+
1
`
o
f
f
t
h
e
m
,
w
h
i
c
h
i
s
s
t
i
l
l
p
o
l
y
n
o
m
i
a
l
t
o
w
r
i
t
e
d
o
w
n
.
I
f
`
G
`
h
a
s
a
H
a
m
i
l
t
o
n
c
i
r
c
u
i
t
t
h
e
o
p
t
i
m
u
m
i
s
e
x
a
c
t
l
y
`
n
`
,
s
o
t
h
e
a
l
g
o
r
i
t
h
m
m
u
s
t
r
e
t
u
r
n
a
t
o
u
r
o
f
c
o
s
t
a
t
m
o
s
t
`
ρ
·
n
`
.
I
f
`
G
`
h
a
s
n
o
n
e
,
e
v
e
r
y
t
o
u
r
u
s
e
s
a
n
o
n
-
e
d
g
e
a
n
d
c
o
s
t
s
m
o
r
e
t
h
a
n
`
ρ
·
n
`
.
S
o
t
h
e
r
e
t
u
r
n
e
d
c
o
s
t
d
e
c
i
d
e
s
w
h
e
t
h
e
r
a
H
a
m
i
l
t
o
n
c
i
r
c
u
i
t
e
x
i
s
t
s
,
a
n
d
t
h
e
w
h
o
l
e
p
r
o
c
e
d
u
r
e
i
s
p
o
l
y
n
o
m
i
a
l
.
□
The lab uses 2 rather than ρ · n + 1, because 2 is what the decision reduction needs and small numbers are what a five-city enumeration can show. The inapproximability variant is the same gadget with the off-edge distance raised, and this panel cannot do that — its distances are derived from the graph rather than typed, so the variant is an argument here and a slider in “The Hypothesis Doing the Work”. What it means for the rest of the course is stark: approximation is not available for this problem as stated, so the next approximation of a tour will come with a hypothesis attached.