Checking if a Hamilton Cycle exists in a dense graph

Question

A few definitions first:

Definition 1

A graph G = (V, E) is called ``dense'' if for each pair of non-adjacent vertices u and v, d(u) + d(v)>=n where n = |V| and d(*) denotes the degree of the vertex *

Definition 2

A ``Hamiltonian cycle'' on G is a sequence of vertices ( vi1, vi2,....vin, vi1 ) such that vil != vih for all l!=h and { vil, vil} is an edge of G.

The problem is: write a program that, given a dense undirected graph G = (V; E) as input, determines whether G admits a Hamiltonian cycle on G and outputs that cycle, if there is one, or outputs ``N'' if there is none.

my solution is to find all the possible paths starting from a source and to check if a path exists that gets back to this source. Unfortunately, this solution is not efficient.

any suggestions? Thank you.

[This](http://stackoverflow.com/questions/1387725/what-is-dynamic-programming-algorithm-for-finding-a-hamiltonian-cycle?rq=1) uses dynamic programming to do the job. — denahiro, Jun 25 '12 at 08:55
Though the above post mentions it, I'll mention it as well to save some searching time - an algorithm exists, but it's not polynomial time. The decision version of Hamiltonian Cycle is NP-Hard. You're not going to find an "efficient" solution - well, if you do, then the computer science community would love to hear it. :) — adelbertc, Jun 25 '12 at 08:58
According to Ore's theorem (http://en.wikipedia.org/wiki/Ore%27s_theorem), graphs satisfying Definition 1 always have a Hamiltonian cycle. — Tamás, Jun 25 '12 at 08:59

score 7 · Accepted Answer · answered Jun 25 '12 at 09:00

7

According to Ore's theorem, graphs satisfying Definition 1 always have a Hamiltonian cycle, and Palmer's algorithm will give you one in O(n²).

answered Jun 25 '12 at 09:00

Tamás

47,239
12
105
124

score -2 · Answer 2 · answered Jun 25 '12 at 08:54

-2

The problem is NP-hard. So I would not expect any solution to be much faster than brute-force.

answered Jun 25 '12 at 08:54

timos

2,637
18
21

Is it NP-hard even on dense graphs? – avakar Jun 25 '12 at 08:58
@avakar: No, it isn't; see my answer. – Tamás Jun 25 '12 at 09:00
it's a trick....since the given graph is dense, it has Hamilton path! but Tamas, you should also output that path which will not improve the solution! – Traveling Salesman Jun 25 '12 at 09:04
oh sorry, when I answered the question, the definition of density was not included in the question, so I just gave an answer for the common case. – timos Jun 25 '12 at 09:08

Checking if a Hamilton Cycle exists in a dense graph

2 Answers2

Linked