A parallel algorithm for computing the critical independence number and related sets

Abstract

An independent set I_c is a critical independent set if ∣I_c∣ − ∣N(I_c)∣ ≥ ∣J∣ − ∣N(J)∣, for any independent set J. The critical independence number of a graph is the cardinality of a maximum critical independent set. This number is a lower bound for the independence number and can be computed in polynomial-time. The existing algorithm runs in O(n^2. 5 √(m/log n)) time for a graph G with n = ∣V(G)∣ vertices and m edges. It is demonstrated here that there is a parallel algorithm using n processors that runs in O(n^1. 5 √(m/log n)) time. The new algorithm returns the union of all maximum critical independent sets. The graph induced on this set is a König-Egerváry graph whose components are either isolated vertices or which have perfect matchings.