On the parallel complexity of Hamiltonian cycle and matching problem on dense graphs. (English) Zbl 0782.68055

Dahlhaus, Elias; Hajnal, Péter; Karpinski, Marek

J. Algorithms 15, No. 3, 367-384 (1993).

Summary: Dirac’s classical theorem [G. A. Dirac, Some theorems on abstract graphs, Proc. Lond. Math. Soc. 2, 69-81 (1952)] 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 a such graphs. Our algorithm uses a linear number of processors and is optimal up to a polylogarithmic factor. The algorithm works in \({\mathcal O}(\log^ 4n)\) parallel time and uses linear number of processors on a CREW-PRAM. Our method bears some resemblance to R. J. Anderson’s [Combinatorica 7, 315-326 (1987; Zbl 0641.68105)] RNC algorithm 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^ 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 (minimum degree is at least \(({1 \over 2}-\varepsilon) | V |)\) is as hard as the same problem for all graphs, and interestingly the problem of finding a Hamiltonian cycle becomes \(NP\)- complete.

MSC:

68Q25	Analysis of algorithms and problem complexity
68R10	Graph theory (including graph drawing) in computer science
68W15	Distributed algorithms
05C85	Graph algorithms (graph-theoretic aspects)

Keywords:

matching; dense graphs; Hamiltonian cycle; CREW-PRAM; linear number of processors

Citations:

Zbl 0641.68105