Claw-free Graph - Independent Sets

Independent Sets

An independent set in a line graph corresponds to a matching in its underlying graph, a set of edges no two of which share an endpoint. As Edmonds (1965) showed, a maximum matching in any graph may be found in polynomial time; Sbihi (1980) extended this algorithm to one that computes a maximum independent set in any claw-free graph. Minty (1980) (corrected by Nakamura & Tamura 2001) independently provided an alternative extension of Edmonds' algorithms to claw-free graphs, that transforms the problem into one of finding a matching in an auxiliary graph derived from the input claw-free graph. Minty's approach may also be used to solve in polynomial time the more general problem of finding an independent set of maximum weight, and generalizations of these results to wider classes of graphs are also known.

As Sbihi observed, if I is an independent set in a claw-free graph, then any vertex of the graph may have at most two neighbors in I: three neighbors would form a claw. Sbihi calls a vertex saturated if it has two neighbors in I and unsaturated if it is not in I but has fewer than two neighbors in I. It follows from Sbihi's observation that if I and J are both independent sets, the graph induced by I ∪ J must have degree at most two; that is, it is a union of paths and cycles. In particular, if I is a non-maximum independent set, it differs from any maximum independent set by cycles and augmenting paths, induced paths which alternate between vertices in I and vertices not in I, and for which both endpoints are unsaturated. The symmetric difference of I with an augmenting path is a larger independent set; Sbihi's algorithm repeatedly increases the size of an independent set by searching for augmenting paths until no more can be found.

Searching for an augmenting path is complicated by the fact that a path may fail to be augmenting if it contains an edge between two vertices that are not in I, so that it is not an induced path. Fortunately, this can only happen in two cases: the two adjacent vertices may be the endpoints of the path, or they may be two steps away from each other; any other adjacency would lead to a claw. Adjacent endpoints may be avoided by temporarily removing the neighbors of v when searching for a path starting from a vertex v; if no path is found, v can be removed from the graph for the remainder of the algorithm. Although Sbihi does not describe it in these terms, the problem remaining after this reduction may be described in terms of a switch graph, an undirected graph in which the edges incident to each vertex are partitioned into two subsets and in which paths through the vertex are constrained to use one edge from each subset. One may form a switch graph that has as its vertices the unsaturated and saturated vertices of the given claw-free graph, with an edge between two vertices of the switch graph whenever they are nonadjacent in the claw-free graph and there exists a length-two path between them that passes through a vertex of I. The two subsets of edges at each vertex are formed by the two vertices of I that these length-two paths pass through. A path in this switch graph between two unsaturated vertices corresponds to an augmenting path in the original graph. The switch graph has quadratic complexity, paths in it may be found in linear time, and O(n) augmenting paths may need to be found over the course of the overall algorithm. Therefore, Sbihi's algorithm runs in O(n3) total time.