Optimal Parallel Algorithm for the Hamiltonian Cycle Problem on Dense Graphs

TitleOptimal Parallel Algorithm for the Hamiltonian Cycle Problem on Dense Graphs
Publication TypeTechnical Report
Year of Publication1989
AuthorsDahlhaus, E., Hajnal P., & Karpinski M.
Other Numbers541

Dirac's classical theorem asserts that, if every vertex of a graph G on n vertices has degree at least n/2, then G has a Hamiltonian cycle. We give a fast parallel algorithm on a CREW-PRAM to find a Hamiltonian cycle in such graphs. Our algorithm uses a linear number of processors and is optimal up to a polylogarithmic factor. The algorithm works in O((log (superscript 4)) n) parallel time and uses linear number of processors on a CREW-PRAM. Our method bears some resemblance to Anderson's RNC algorithm [An] for maximal paths: we, too, start from a system of disjoint paths and try to glue them together. We are, however, able to perform the base step (perfect matching) deterministically. We also prove that a perfect matching in dense graphs can be found in NC(superscript 2). The cost of improved time is a quadratic number of processors.On the negative side, we prove that finding an NC algorithm for perfect matching in slightly less dense graphs (1/2 - epsilon) |V| is as hard as the same problem for all graphs, and interestingly the problem of finding a Hamiltonian cycle becomes NP-complete.

Bibliographic Notes

ICSI Technical Report TR-89-042

Abbreviated Authors

E. Dahlhaus, P. Hajnal, and M. Karpinski

ICSI Publication Type

Technical Report