Parallel Algorithms for Intersection Graphs

Abstract

Intersection graphs have often been used to model special structure in graph problems for both practical and theoretical reasons. Often problems can be solved efficiently for a restricted class of graphs that are provably hard for graphs in general. In this thesis, we examine parallel (i.e. $NC$) algorithms for exploiting the special structure of different types of intersection graphs to solve common graph problems. First, we show how to recognize whether a graph belongs to one of the special families of intersection graphs. Only after this has been done can we take advantage of the properties of a class of intersection graphs. Let $\cal F$ be a family of nonempty sets. Then the intersection graph of $\cal F$ is obtained by representing each set in $\cal F$ by a vertex and connecting two vertices if and only if their corresponding sets have a nonempty intersection. In this dissertation, several types of intersection graphs will be examined, among them interval, comparability, chordal, path, and circle graphs. Interval and comparability graphs arise often when solving scheduling problems. Chordal graphs have applications in solving sparse systems of linear equations and in relational database theory. Each of these classes of intersection graphs is closed under a natural graph composition operation, namely one of modular composition, clique identification, and split composition. In this thesis, we show that the number of intersection representations for a graph in one of these classes depends on how the graph was composed from indecomposable graphs. Also, we show how to efficiently decompose any graph (i.e. perform that inverse of the above composition operations) in parallel. Often if we can solve a problem efficiently on the indecomposable pieces of a graph, then we can solve this same problem efficiently on the graph itself in parallel. Thus we can extend many of our results on special classes of intersection graphs to more general classes of graphs.