An Efficient Parallel Algorithm that Finds Independent Sets of Guaranteed Size

Every graph with n vertices and m edges has an independent set containing at least n² / (2m + n) vertices. This paper presents a parallel algorithm that finds an independent set of this size and runs in O (³ n) time on a CROW PRAM with O ( (m + n) (m, n) / ² n) processors, where (n, m) is a functional inverse of Ackerman’s function. The ideas used in the design of this algorithm are also used to design an algorithm that, with the same resources, finds a vertex coloring satisfying certain minimality conditions.