NC Algorithms for the Clique Separator Decomposition

Abstract

We give the first NC algorithm for finding a clique separator decomposition of a graph, that is, a series of cliques whose removal disconnects the graph. This algorithm allows one to extend a large body of results which were originally formulated for chordal graphs to other classes of graphs. Our algorithm is a parallel version of Tarjan's sequential algorithm for solving this problem. The decomposition can also be used to find NC algorithms for some optimization problems on special families of graphs, assuming these problems can be solved in NC for the prime graphs of the decomposition. These optimization problems include: finding a maximum-weight clique, a minimum coloring, a maximum-weight independent set, and a minimum fill-in elimination ordering. We also give the first parallel algorithms for solving these problems by using the clique separator decomposition. Our maximum-weight independent set alforithm applied to chordal graphs yields the most efficient known parallel algorithm for finding a maximum-weight independent set of a chordal graph.