05.12.2008

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 its optimal up to a polylogarithmic factor. The algorithm works in O(log⁴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². 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 (minimum degree is at least (1/2 - ε)|V|) is as hard as the same problem for all graphs, and interestingly the problem of finding a Hamiltonian cycle become NP-complete.