3
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ Where did you read it? $\endgroup$
    – saulspatz
    Jul 1, 2018 at 0:19
  • 1
    $\begingroup$ It is NP-complete for arbitrary graphs, not all graphs. This means that there exists a polynomial time algorithm which, given an arbitrary graph, solves the Hamiltonian path problem on it iff P = NP. There are certainly subsets of graphs for which the problem is efficiently solvable. $\endgroup$
    – theyaoster
    Jul 1, 2018 at 0:24
  • 1
    $\begingroup$ The Hamiltonian path problem is very easy for cycles, for trees, and probably for lots of other graphs. $\endgroup$ Jul 1, 2018 at 1:03
  • $\begingroup$ So to prove that P=NP you would have to prove that every class of graphs is solvable in polynomial time? $\endgroup$ Jul 1, 2018 at 18:04
  • $\begingroup$ I´m not sure if I understood the question in the past. Some graphs can be solved in O(1) with specific algorithms for a category of graphs, but an algorithm must give an exact result to all possible graphs within a general classification of graphs. I don't know where is the border of the classification to be general or not, but it seems to be as general as possible, not a category deduced from a class. $\endgroup$
    – Ixer
    Feb 28, 2020 at 16:07

3 Answers 3

3
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .