Book Chapter

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

StatusPublished
Title of seriesAdvances in Intelligent Systems and Computing
Number in series1228
Publication date31/12/2020
Publication date online04/07/2020
URLhttp://hdl.handle.net/1893/31424
PublisherSpringer International Publishing
Place of publicationCham, Switzerland
ISSN of series2194-5357
ISBN9783030522483
eISBN9783030522490