On Independent Cliques and Linear Complementarity Problems
share
In recent work (Pandit and Kulkarni [Discrete Applied Mathematics, 244 (2018), pp. 155--169]), the independence number of a graph was characterized as the maximum of the ℓ_1 norm of solutions of a Linear Complementarity Problem () defined suitably using parameters of the graph. Solutions of this LCP have another relation, namely, that they corresponded to Nash equilibria of a public goods game. Motivated by this, we consider a perturbation of this LCP and identify the combinatorial structures on the graph that correspond to the maximum ℓ_1 norm of solutions of the new LCP. We introduce a new concept called independent clique solutions which are solutions of the LCP that are supported on independent cliques and show that for small perturbations, such solutions attain the maximum ℓ_1 norm amongst all solutions of the new LCP.
READ FULL TEXT