This may be the hardest problem description to understand that I’ve done. I’m still not sure I really understand the problem, let alone the reduction. So I apologize in advance for what you’re about to read.
The problem: Traveling Salesman Polytope Non-Adjacency. This is problem MP8 in the appendix.
The description: I’ve got a lot of this definition from the paper by Papadimitriou that has the reduction. We’ll take it slowly:
Suppose we have a complete, undirected, weighted graph G=(V, E). Let |V| = n. This means that |E| = n*(n-1)/2. We can number these edges, and then denote whether a potential tour is “using” an edge or not by a 0/1 vector. So a vector (0,1,1,0,1,0) means that the solution we’re considering uses edges 2,3, and 5. (This may or may not be a legal tour). Each legal Hamiltonian Cycle can be represented as one of these vectors. This gives us a set of 0/1 vectors. We can think of these vectors as points in Rn. We then want to talk about the convex hull of these points.
Two vertices on this convex hull are defined to be “adjacent” if they are connected by an edge on the convex hull.
So, the problem asks: Given two Hamiltonian Cycles on G, are they non-adjacent on this convex hull?
(Yes, it’s weird that the problem never uses the distances between the vertices. I think this is really “Hamiltonian Cycle Polytope Non-Adjacency”. In fact, I think this makes more sense because the graph that is built in the reduction is not a complete graph)
Example: This is pretty hard to visualize, so let’s start with a simple graph:
Let’s list edges in alphabetical order in our vector. The vector will have 6 elements in alphabetical order: ab, ac, ad, bc, bd, cd
So the tours we have are:
- ABCDA, represented as (1,0,1,1,0,1)
- ABDCA, represented as (1,1,0,0,1,1)
- ACBDA, represented as (0,1,1,1,1,0)
..and that’s really it. All of the other tours are either reversals of the above (such as ADCBA), or an above tour shifted by starting at a different point (like BCDAB), which use the same edges and thus create the same vectors.
So, we are left with 3 points in 6-dimensional space. Obviously, any 2 points in that space are adjacent. If we start with a graph with 5 vertices:
we have 10 dimensions to our vector, for the edges ab, ac, ad, ae, bc, bd, be, cd, ce, and de. We also have 12 tour vectors. I won’t list them all, but for example, the tour ABCDEA would be represented by (1,0,0,1,1,0,0,1,0,1). In this case, the need to define what the convex hull of those points are, and whether 2 tours are adjacent becomes harder to see.
Papadimitriou uses 3SAT. So we’re given a set of m clauses over p variables, and we need to build a graph and two tours. The graph he builds is made up of a series of widgets. These widgets are designed to force certain edges to be used if the graph is to have a Hamiltonian Cycle. The idea is that he constructs the widgets in a way that we can construct 2 cycles that are non-adjacent if and only if the formula was satisfiable. So for example, here is his “exclusive or” subgraph (p. 316 of the paper):
In this subgraph, a Hamiltonian Cycle needs to go from u to u’ or v to v’ (it can’t do both, it can’t do neither). By constructing ever-more complicated versions of this, he builds a graph. Here’s how it looks for the formula B = (x1, x2, x3) ∧ (x1, x2, ~x3) ∧ (~x1, ~x2, ~x3) (p. 319 of the paper):
The bold lines in the figure above correspond to setting all variables to true. There is also a circuit corresponding to making all variables false. (We assume this satisfies at least one clause because if it didn’t, we have a Satisfiability instance where each clause has at least one positive literal, which is trivially satisfiable). It turns out that every edge in this graph belongs to at least one of these two cycles. For these two cycles to not be adjacent in the polytope, there needs to be some other circuit “between” them. This circuit corresponds to a legal way to set all of the variables to make all clauses true. If no such circuit exists (and the formula is not satisfiable), then the 2 tours are adjacent.
Difficulty: 9. I can see what he’s doing, but I really have trouble following how he gets there. Part of the difficulty with this problem is that it’s such a weird non-intuitive (to me) definition of “adjacency”. I wonder if there is a better one out there. Another source of difficulty is what I think of as confusion between TSP and HC. The crazy widgets don’t help either.