Input: shortest path metric in a 2-edge-connected unweighted graph G in which every vertex has degree 3.

Output: 4/3 approximation to TSP

Algorithm:

1) Let T be any depth-first-search tree.

2)

**Define removable pairs**as follows: each back edge goes into some vertex, call it v, and (if v is not the root) is paired with a tree edge from v to the child of v. ("the" child, because the graph is cubic).

3) Take M, a random perfect matching of G such that each edge is in M with probability 1/3 (known from some 1980's discrete math publications).

4)

**For each edge e of M that is in a removable pair, remove e from G**. For each edge e of M that is not in a removable pair, add e to G, creating a duplicate edge.

5) Output an Eulerian tour of resulting multigraph.

Analysis of correctness: in the multigraph, every vertex has even degree, 2 or 4, and, given the definition of removable pairs, it is not hard to convince oneself that it is still connected, so it's Eulerian.

Analysis of cost: G has (3/2)n edges. T has n edges. (Almost) every back edge is in a removable pair, so there are (n/2) removable pairs, each pair with 2 edges, for a total of (n/2)*2=n removable edges. The other (n/2) edges are unremovable. The expected size of the output is:

(#edges of G)+(# unremovable)*prob(in M) - (# removable)*prob(in M)=(3/2)n+(n/2)*(1/3)-(n)*(1/3)=(4/3)n,

give or take a few.

This is so simple that it could probably be taught at the senior undergraduate level.

And that concludes my posts about TSP, for now.

Thanks a lot for the nice blog posts!

ReplyDeleteFor those that are interested, illustrations of this algorithm on cubic graphs are available on slides 10-13 of

http://algo.epfl.ch/~osven/presentations/graphTSP.pptx