Using Bounded Degree Spanning Trees in the Design of Efficient Algorithms on Claw Free Graphs

Abstract

Claw-free graphs are graphs that do not have $K_{1,3}$ as an induced subgraph. Line graphs, a special case of claw-free graphs, are the intersection graphs of edges in simple graphs. We show how to compute efficiently in parallel a binary tree that will be a rooted spanning tree of the claw-free graph. Every binary tree contains at least one edge whose removal partitions the tree into two subtrees of nearly equal cardinality, and this separator can be found efficiently in parallel. We solve problems on claw-free graphs by a divide-and-conquer strategy. The advantage of our partition is that the vertices in each set induce a connected subgraph. The problems are solved for the two subgraphs, and then the results are combined to get a solution for the entire graph. Both the problem of finding a perfect matching in claw-free graphs and the problem of reconstructing a root graph from a line graph are amenable to this approach. We present a nearly optimal parallel NC algorithm for computing a perfect matching that runs in time $O(log^{2}n)$ with $O(n + m)$ processors on an EREW PRAM. Also, we present an efficient parallel reconstruction of root graphs form line graphs. If G = (V,E) denotes a line graph, then the algorithm runs in $O(log\vert V \vert)$ time using $O(\vert E \vert)$ processors in the CRCW PRAM model. It is optimal up to a polylogarithmic factor. Previously, it was known how to reconstruct the root graph in NC using a large (though polynomial) number of processors; this is the first algorithm that employs a linear number of processors.