Give me an example of a graph that has a Hamilton path that cannot be found with a greedy heuristic.

Question

Give me an example of a graph that has a Hamilton path that cannot be found with a greedy heuristic.

I have yet to find a graph that can fulfill these requirements, I thought a Peterson graph might do, but it can work if you chose the outermost cycle first, and then go into the star. Since it works some of the time, it can be solved by the greedy heuristic.

Does this exist at all?

Thanks!

Answer 1

Any Hamiltonian path can be found by the greedy heuristic if you happen to look at the graph in the right order.

If $G$ has a Hamiltonian path, order the vertices $v_1, v_2, \dots, v_n$ in the order that they are visited in the path. Then the greedy strategy of "start at $v_1$, and go to the first unvisited neighbor of a vertex" will go from $v_1$ to $v_2$ to $v_3$ and so on, finding exactly this path.

The trouble with the greedy heuristic is that most of the time, the order you choose will happen not to be the right one.

(Similarly, the algorithm "consider all the vertices in a random order, and see if they form a Hamiltonian path" will work with probability $\frac{1}{n!}$.)