On independent cliques and linear complementarity problems

DOI10.1007/S13226-022-00217-WMaRDI QIDQ2095085zbMATH OpenOpenAlexFDO

Authors Karan N. Chadha, Ankur A. Kulkarni

Publication date 9 November 2022

Published in Indian Journal of Pure \& Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1811.09798

zbMATH Keywords

cliquesdominating setsindependent setslinear complementarity problems

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33) Noncooperative games (91A10)

Abstract: 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 $el{l}_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 $el{l}_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 $el{l}_1$ norm amongst all solutions of the new LCP.

Recommendations

• A linear complementarity based characterization of the weighted independence number and the independent domination number in graphs
• On the convexity of independent set games
• The integer linear complementarity problem
• Generalized linear complementarity in a problem of \(n\)-person games
• scientific article; zbMATH DE number 2043365

Cites work

• A complementary pivoting approach to the maximum weight clique problem
• A fast branching algorithm for cluster vertex deletion
• A linear complementarity based characterization of the weighted independence number and the independent domination number in graphs
• An LPCC approach to nonconvex quadratic programs
• Graphs with unique maximum independent sets
• scientific article; zbMATH DE number 53115 (Why is no real title available?)
• scientific article; zbMATH DE number 192986 (Why is no real title available?)
• Maxima for Graphs and a New Proof of a Theorem of Turán
• On a polynomial fractional formulation for independence number of a graph
• On linear programs with linear complementarity constraints
• On the variational equilibrium as a refinement of the generalized Nash equilibrium
• On unique independent sets in graphs
• Public goods in networks
• Refinement of the equilibrium of public goods games over networks: efficiency and effort of specialized equilibria
• The combinatorics of pivoting for the maximum weight clique.
• The maximum independent union of cliques problem: complexity and exact approaches

Cited in

(3)

• A linear complementarity based characterization of the weighted independence number and the independent domination number in graphs
• Aggregate play and welfare in strategic interactions on networks
• On NP-hardness of the clique partition -- independence number gap recognition and related problems

This page was built for publication: On independent cliques and linear complementarity problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2095085)