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

Ermelinda DeLaViña, Craig Eric Larson


An independent set Ic is a critical independent set if ∣Ic∣ − ∣N(Ic)∣ ≥ ∣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(n2. 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(n1. 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.


critical independent set, critical independence number, independence number, matching number, König-Egerváry graph

Full Text:


DOI: https://doi.org/10.26493/1855-3974.165.b8b

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications