Finding Hamiltonian cycles in cubic planar graphs

Question

I have relatively small (40-80 nodes) cubic (3-regular) planar graphs, and I have to decide their Hamiltonicity. I am aware of the fact that this task is NP-complete, but I hope for asymptotically exponential time algorithms that are nevertheless very fast for the graph size I am interested in.

Answer 1

40 nodes seems doable. You're choosing 40 of 60 edges to include.

Let's try a depth-first search.

To start, pick a vertex V. You will need to exclude exactly one of its 3 incident edges. Try these 3 possibilities one at a time. When you choose an edge to exclude, you are forcing the inclusion of 4 edges. After this, we'll call the vertices of the excluded edge "used".

If you could repeat this process 10 times, you would have chosen all 40 edges, searching only 3^10 (59049) possibilities. Of course, you'll run out of "isolated" vertices after enough edges have been determined.

But, we now have an idea for an algorithm. At each step, try picking a vertex with the fewest "used" neighbors. Actually, picking a vertex with 2 used neighbors is best, since the used edge is forced. I'm not sure if picking a vertex with 1 or 0 used neighbors is the next best. Try both ways! (And 3 used neighbors indicates a failed search)

When we're done picking edges, check if they form a single cycle.

Do you have a few sample graphs? I might try a simple implementation.