Article ID Journal Published Year Pages File Type
6871159 Discrete Applied Mathematics 2018 15 Pages PDF
Abstract
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.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,