|
| | | | |
| | | |
| Stat |
Members: 3644
Articles: 2'499'343
Articles rated: 2609
16 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
A linear complementarity based characterization of the weighted independence number and the independent domination number in graphs | | Parthe Pandit
; Ankur A. Kulkarni
; | | Date: |
16 Mar 2016 | | Abstract: | The linear complementarity problem is a continuous optimization problem that
generalizes convex quadratic programming, 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 $ell_1$ norm over the solution set of a linear
complementarity problem (LCP). The minimum $ell_1$ norm of solutions of this
LCP is a lower bound on the independent domination number of the graph. Unlike
the case of the maximum $ell_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 obtain a few graph theoretic results. In particular, we provide a
stronger variant of the Lov’{a}sz theta of a graph. We then provide sufficient
conditions for a graph to be well-covered, i.e., for all maximal independent
sets to also be maximum. This condition is also shown to be necessary for
well-coveredness if the graph is a forest. 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. | | Source: | arXiv, 1603.5075 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER