8
$\begingroup$

A graph whose closure is the complete graph is Hamiltonian by the Bondy-Chvátal theorem, but I haven't found a polynomial algorithm for finding a Hamiltonian cycle in such a graph. Is there one that we know of?

https://en.wikipedia.org/wiki/Bondy%E2%80%93Chv%C3%A1tal_theorem#Bondy.E2.80.93Chv.C3.A1tal_theorem

I don't see that class here http://www.graphclasses.org/classes/problem_Hamiltonian_cycle.html

$\endgroup$

2 Answers 2

5
$\begingroup$

Tony's method works in the general case. Let $e_1, e_2, \ldots, e_N$ be the edges that are added to $G$, in the order they are added, to make the complete graph. Choose an arbitrary hamiltonian cycle in the complete graph. Now remove $e_N$. If $e_N$ was in the cycle, you can find a new cycle that avoids it by the cross-over technique that Tony explains. Then remove $e_{N-1}$ in the same way. Continue until you removed all the edges that were added. Since each step takes time $O(n)$, the total time is $O(nN)=O(n^3)$. I don't believe this is best possible and wouldn't be surprised if this can be implemented in time $O(n^2)$.

$\endgroup$
2
  • $\begingroup$ Why not start by removing all (or half, say) of the new edges not on the cycle? (or even 1/k, where k is the number of new edges on the cycle.) $\endgroup$ May 1, 2014 at 23:21
  • $\begingroup$ If any new edges are removed, the degree sum condition may not be met when cycle edges are removed. That condition is a necessary part of the argument that a new cycle can be found. $\endgroup$ May 2, 2014 at 0:38
3
$\begingroup$

In the case that your graph satisfies the conditions of Ore's theorem (so that it's Ore closure is $K_n$ after 'one step'), there is an easy algorithm to find a Hamilton cycle.

Arbitrarily arrange the vertices $v_1, \dots, v_n$ in a circle. If all consecutive vertices $v_i$ and $v_{i+1}$ are adjacent in $G$ (subscripts are read mod $n$), then we are done. Otherwise, if $v_i$ and $v_{i+1}$ are non-adjacent, find an index $j$ such that $v_i$ is adjacent to $v_j$ and $v_{i+1}$ is adjacent to $v_{j+1}$. Such an index $j$ is guaranteed to exist by Ore's condition, and can be found in time $O(n)$. Change the ordering of the vertices in the obvious way, and note that the number of non-adjacent consecutive vertices has gone down. After at most $n$ steps, we will output a Hamilton cycle, so this takes $O(n^2)$ in total.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.