A linear complementarity based characterization of the weighted independence number and the independent domination number in graphs

The linear complementarity problem is a continuous optimization problem that generalizes convex quadratic programming, characterization of Nash equilibria of bimatrix games and several such problems. This paper presents a continuous optimization formulation for the weighted independence number of a graph by characterizing it as the maximum weighted ℓ1 norm over the solution set of a linear complementarity problem (LCP). The minimum ℓ1 norm of solutions of this LCP forms a lower bound on the independent domination number of the graph. Unlike the case of the maximum ℓ1 norm, this lower bound is in general weak, but we show it to be tight if the graph is a forest. Using methods from the theory of LCPs, we then obtain a stronger variant of the Lovász theta and a new sufficient condition for a graph to be well-covered, i.e., for all maximal independent sets to also be maximum. This latter condition is also shown to be necessary for well-coveredness of forests. Finally, the reduction of the maximum independent set problem to a linear program with (linear) complementarity constraints (LPCC) shows that LPCCs are hard to approximate.