Paper Info
Title
A linear complementarity based characterization of the weighted independence number and the independent domination number in graphs.
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.
Year
DOI
Venue
2018
10.1016/j.dam.2018.02.022
Discrete Applied Mathematics
Keywords
DocType
Volume
Weighted independence number in graphs,Independent domination number in graphs,Linear complementarity problems,Well covered graphs,Lovasz theta,Continuous formulations of discrete problems
Journal
244
ISSN
Citations 
PageRank 
0166-218X
2
0.58
References 
Authors
12
2
Name
Order
Citations
PageRank
Parthe Pandit121.59
Ankur A. Kulkarni210620.95