DIMACS TR: 93-81

Fast Parallel Algorithms for Finding Hamiltonian Cycles and Trees in Graphs

Author: Gabor Sarkozy


Suppose 0 < delta < 1 is given. We call a graph, G, on n vertices a delta- Posa graph if its degree sequence d_1 <= d_2 <= ... <= d_n satisfies: for 1<= k <= n, d_k >= min { k + delta n, n/2 }. An NC^4-algorithm is presented which accepts as input a delta-Posa graph and produces a Hamiltonian cycle in G as an output. This is a significant improvement on the previous best NC-algorithm for the problem , which finds a Hamiltonian cycle only in Dirac graphs ( delta (G) >= n/2 where delta (G) is the minimum degree in G ). The difficulty of the problem is indicated by the fact , that if alpha < 1/2, the Hamiltonian cycle problem restricted to alpha-dense graphs ( delta (G) >= alpha n ) becomes NP-complete. A related NC^4-algorithm is also presented which accepts as inputs a bounded degree tree T on n vertices, and a graph G on also n vertices with delta (G) >= ( 1/2 + epsilon ) n, and it finds a copy of T in G.

Paper only.
DIMACS Home Page