Search code examples
algorithmgraphtraveling-salesmanhamiltonian-cycle

Palmer's Algorithm for Hamiltonian cycles

In a "dense" graph, I am trying to construct a Hamiltonian cycle using Palmer's Algorithm. However, I need more explanation for this algorithm because it does not work with me when I implement it. It seems that there is an unclear part in Wikipedia's explanation.

I would be thankful if someone explains it more clearly or give me some links to read.

Here's the algorithm statement:

Palmer (1997) describes the following simple algorithm for constructing a Hamiltonian cycle in a graph meeting Ore's condition. Arrange the vertices arbitrarily into a cycle, ignoring adjacencies in the graph. While the cycle contains two consecutive vertices vi and vi + 1 that are not adjacent in the graph, perform the following two steps:

  • Search for an index j such that the four vertices vi, vi + 1, vj, and vj + 1 are all distinct and such that the graph contains edges from vi to vj + 1 and from vj to vi + 1

  • Reverse the part of the cycle between vi + 1 and vj (inclusive).

To be more specific, I do not get the part where they say: "Arrange the vertices arbitrarily into a cycle" in this case, is this right to do: 0,1,2,3,4,0

and what do they mean by: "Reverse the part of the cycle"?

Solution

  • Indeed, wikipedia's description of the algorithm is¹ was wrong. Palmer's own description is

    1. Step 0. Arrange the vertices in a circle.

    2. Step 1. Look around the boundary, say in the counterclockwise direction, for consecutive nonadjacent vertices, i.e., a gap. If there are no gaps, quit with the spanning cycle on the boundary. Otherwise, look for a pair of crossing chords from the vertices of the gap to some other pair of consecutive vertices that may or may not be adjacent (possible gap 2).

      If found, (i.e., gap 1 was good!), simply rearrange the circular order of the vertices in the obvious way so that the two chords become edges on the boundary and the gaps are switched to the interior. Each time we play this game of criss-cross successfully, one or two gaps on the boundary of the circular arrangement of vertices are replaced by two edges. Otherwise repeat Step 1 with the next gap.

      Continue until the spanning cycle is on the boundary, or until every gap is bad.

    You need a pair of crossing chords, i.e. you need edges

    v_i <-> v_j
v_{i+1} <-> v_{j+1}

    That way, by reversing the part from v_{i+1} to v_j (inclusive), you move the vertex v_j - adjacent to v_i in the graph - next to v_i in your cycle, and the vertex v_{i+1} - adjacent to v_{j+1} in the graph - is moved next to v_{j+1} in the cycle. Thus we obtain two new pairs of neighbours in the cycle that are adjacent in the graph, (v_i, v_j) and (v_{i+1}, v_{j+1}), and possibly destroy one pair of cycle-neighbours that are adjacent in the graph, (v_j, v_{j+1}). The number of pairs of cycle-neighbours that are adjacent in the graph increases by 1 or by two each step, so the algorithm terminates.

    With the wrong indexing of wikipedia, moving v_j next to v_i and v_{i+1} next to v_{j+1} need not generate a new pair of cycle-neighbours that are adjacent in the graph, thus the algorithm need not terminate.

    So let's play it through for your example

    E = { (1,2), (1,3), (1,6), (3,2), (3,4), (5,2), (5,4), (6,4), (6,5) }

    arranging it as 1426351 initially (no adjacent neighbours).

    The first pair of cycle-neighbours not adjacent in the graph is (1,4) = (v_1,v_2). Scan for an index j > 2 such that v_j is adjacent to v_1 and v_{j+1} to v_2, the first such occurrence is j = 3. Now reverse the part 4...2 in the cycle (in this case, there's no vertex between 4 and 2), giving the next cycle

    1234561  // index in cycle
1246351  // vertex

    with two pairs of adjacent neighours ((1,2) and (4,6)). The first index i with v_i not adjacent to v_{i+1} is 2. Scan for the first j > 3 such that v_j is adjacent to v_2 = 2 and v_{j+1} adjacent to v_3 = 4. That gives j = 5. Now the part between v_3 and v_5 (inclusive), giving the next cycle

    1234561  // index in cycle
1236451  // vertex

    Once more, v_3 = 3 is not adjacent to v_4 = 6, so i = 3, j = 5, reversing yields

    1234561  // index in cycle
1234651  // vertex

    Now the only bad pair is (v_6,v_1) = (5,1). The smallest j > 1 such that v_j is adjacent to v_6 = 5 and v_{j+1} to v_1 = 1 is j = 2. Now reverse the part from v_1 to v_2 yielding

    1234561  // index in cycle
2134652  // vertex

    which is a Hamiltonian cycle.

    ¹ I'll fix it in a moment.