The linear complementarity problem is a continuous optimization problem that generalizes convex quadratic programming, 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 is 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 obtain a few graph theoretic results. In particular, we provide a stronger variant of the Lovász theta of a graph. We then provide sufficient conditions for a graph to be well-covered, i.e., for all maximal independent sets to also be maximum. This condition is also shown to be necessary for well-coveredness if the graph is a forest. 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.
The results in REF show that it is hard to find approximate solutions of an LPCC.
A linear complementarity based characterization of the weighted independence number and the independent domination number in graphs
Discrete Applied Mathematics, Volume 244, 31 July 2018, Pages 155-169
Computer Science Mathematics