  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 $\ell_1$ norm of solutions of a Linear Complementarity
Problem (\LCP) 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 $\ell_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 $\ell_1$ norm amongst all
solutions of the new LCP.

Discrete Mathematics;Computer Science and Game Theory;Optimization and Control