Finding the Maximal Independent Sets of a Graph Including the Maximum Using a Multivariable Continuous Polynomial Objective Optimization Formulation

Citation

Heal M & Li J (2020) Finding the Maximal Independent Sets of a Graph Including the Maximum Using a Multivariable Continuous Polynomial Objective Optimization Formulation. In: Arai K, Kapoor S & Bhatia R (eds.) Intelligent Computing. SAI 2020. Advances in Intelligent Systems and Computing, 1228. Cham, Switzerland: Springer International Publishing, pp. 122-136. https://doi.org/10.1007/978-3-030-52249-0_9

Abstract
We propose a multivariable continuous polynomial optimization formulation to find arbitrary maximal independent sets of any size for any graph. A local optima of the optimization problem yields a maximal independent set, while the global optima yields a maximum independent set. The solution is two phases. The first phase is listing all the maximal cliques of the graph and the second phase is solving the optimization problem. We believe that our algorithm is efficient for sparse graphs, for which there exist fast algorithms to list their maximal cliques. Our algorithm was tested on some of the DIMACS maximum clique benchmarks and produced results efficiently. In some cases our algorithm outperforms other algorithms, such as cliquer.

Keywords
Independent set; Continuous optimization; MATLAB; Maximal cliques; Sparse graphs

• Accepted manuscript