Is the Hamiltonian path problem NPC for all graphs?

Question

Is the Hamiltonian path problem NP complete for all graphs or are there some graphs in which the Hamiltonian path problem can be quickly solved? I was reading that for four-connected planar graphs a Hamiltonian path always exists and the computational task of finding one can be done in linear time. Is this true?

Answer 1

There appears to be result showing that the Hamiltonian cycle problem for such graphs is linear time solvable .

However this should not be surprising at all. After all it's the global problems (that consider all the objects involved) that are hard and where the notion of NP completeness makes sense. This doesn't forbid that those problems have a lot of easy instances.

For example consider 3-SAT and some particular implementation of the brute force algorithm that checks all valuations. Now consider the subset of formulas for which the first valuation picked by this algorithm always works. Well that subset is clearly easily solvable by this algorithm.

What's more is that even unsolvable problems like the halting problem have subsets that are easily solvable. What if a counter machine program has no jump instructions at all?

Answer 2

There are many different graph classes where Hamiltonian path problem remains NP-complete, as well as there are many different classes where Hamiltonian path problem can be solved in polynomial time.

Each path $P_n$ obviously has Hamiltonian path. The same is true for a cycle $C_n$ and a complete graph $K_n$. A complete bipartite graph $K_{n_1, n_2}$ has Hamitonian path if and only if $|n_1 - n_2| \le 1$. We can continue this analysis arbitrary long.

Information System on Graph Classes and their Inclusions knows HPP complexity in many different graph classes. Particularly at the moment there are 238 classes where this problem can be solved in linear time, 258 more classes where this problem can be solve in polynomial time and 717 classes where this problem remains NP-complete.

Answer 3

It seems to be true, in fact the Hamiltonian Path Problem is not NP-complete for all kind of Graphs, it is obvious that if you have a 2-regular (planar) graph find a Hamilton Path is trivial.

In some clases of graphs are well known that to find a Hamilton Path is NP-complete, and if one of this were P solvable all of the others must to be P solvable too, and every problem in the universe must too.

You can think that after Chiba and Nishizeki's paper the HC problem for 4-connected planar graphs was NP-complete and before not, so they resolve P=NP, but no. Since Tait´s conjecture it is suspected that find a Hamilton Cycle in any Hamiltonian Graphs is P solvable, so the problem exposed in Chiba and Nishizeki's paper was not NP-complete before.