Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
Abteilung V

Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 1985-1989 Copyright 1985-1989 Universität Bonn, Institut für Informatik, Abt. V

A Fast Parallel Algorithm for Computing All Maximal Cliques in a Graph and the Related Problems
Elias Dahlhaus, Marek Karpinski
[Download PostScript] [Download PDF]

We design a fast parallel algorithm for determining {\bf all} {\it maximal cliques (maximal independent sets)} in an arbitrary graph, working in $O(\log^3(nM))$ parallel time and $O(M^6n^2)$ processors on a CREW-PRAM, where $n$ is the number of vertices and $M$ the number of maximal cliques. It entails the existence of deterministic $NC$-algorithms for several important graph classes with a polynomially bounded number of {\it maximal cliques (maximal independent sets)} in the number of vertices. Our result surprisingly generalizes the recent fast $NC$-algorithms of \ref{NNS} and \ref{DK 1} for computing all maximal cliques on chordal graphs to the arbitrary classes with polynomially many {\it maximal cliques}. Examples of these important classes of graphs besides chordal and strongly chordal graphs \ref{NNS}, \ref{DK} are circle and circular graphs \ref{Go}, \ref{GHS}, $K_4\backslash e$ graphs, circular arc graphs, expander graphs, and edge graphs \ref{Ga}. They arise in a number of applications \ref{Ga}, \ref{TIAS}, \ref{MC}, \ref{GMS}. \medskip All computational solutions for the set of all maximal cliques or maximal independent sets up to now were inherently sequential and strongly restraining efficient parallelization \ref{TIAS}, \ref{CN}. Our result implies that the problem of finding the maximum clique or the lexicographically first maximal clique is efficiently parallelizable for every class of graphs with polynomially many cliques. It stands in contrast to the status of these problems for an unbounded case ($NP$-completeness and $P$-completeness \ref{Co}). It also provides another class of problems (\ref{GK}) with superpolynomial (exponential) monotone lower bound complexity \ref{AB}, \ref{Ra}, and within the uniform Boolean circuits of $O(\log^3n)$ depth and polynomial size. The following general enumeration problem has also been proved to be in $NC$: Given an arbitrary graph $G$, and a natural number $K$ in unary, determine $K$ cliques of $G$ or determine there are less than $K$ cliques in $G$. We apply the new universal algebra method of the Galois connection for the lattice structure of bipartite complete graphs and the recent completeness results on such lattices.\vskip 1cm\noindent

Last Change: 12/01/08 at 18:23:37
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope