Maximum Independent Set Approximation Based on Bellman-Ford Algorithm

This paper presents a new algorithm for approximating the solution of the maximum independent set (MIS) problem. The proposed algorithm takes a novel approach of treating the MIS problem as a least-cost path problem, using an adapted version of Bellman–Ford algorithm, in which all vertices are used as sources, and the cost of a vertex is measured as the number of vertices excluded if this vertex is included in the independent set. Analysis of the proposed algorithm shows that its running time is approximately O(n(n2−m)), where n is the number of vertices and m is the number of edges. Extensive tests against several benchmark graphs and random-generated graphs show a significant improvement of the proposed algorithm over other approximation algorithms, including one of the best known ones such as Greedy algorithm.