Complementary approaches for the computation of the independent number of a graph

C. P. Brás and J. J. Júdice

Abstract

The problem of finding the independent number of an undirected graph is formulated as two equivalent Mathematical Programs with Linear Complementarity Constraints (MPLCC). A multistarting Lemke’s method is introduced for dealing with the first formulation and is able to find a good approximate of the independent number in a finite number of iterations. A sequential complementary algorithm is also discussed for the second formulation and can find the independent number at least in theory. Some computational experience is included to highlight the efficacy of the complementary approaches for computing the independent number of graphs from the Dimacs collection.

Key–Words: Linear Complementarity Problems, Graph Theory, Nonlinear Programming, Global Optimization