TL;DR
This paper introduces a novel way to understand graph properties like the independence number and independent domination number by reformulating them as linear complementarity problems (LCPs). This LCP-based approach leads to new theoretical insights and a more efficient way to formulate these problems as optimization tasks.
What Problem Does This Paper Address?
The paper tackles the challenge of efficiently computing and characterizing two fundamental graph properties: the weighted independence number and the independent domination number. The independence number of a graph is the size of the largest set of vertices where no two vertices are connected by an edge. The weighted version assigns weights to vertices and seeks the independent set with the maximum total weight. The independent domination number is the size of the smallest set of vertices that "dominates" all other vertices (meaning every vertex not in the set is adjacent to at least one vertex in the set), with the additional constraint that the dominating set itself must be independent.
While these problems are well-studied, finding efficient computational methods, especially for weighted versions and for general graphs, remains a significant challenge. Existing approaches often involve complex discrete optimization or less direct continuous formulations. This paper aims to bridge this gap by leveraging the power of linear complementarity problems (LCPs), which are a well-established framework in optimization and game theory.
Methods
The core of this paper is the development of a linear complementarity problem (LCP) formulation for the weighted independence number. Specifically, they show that the maximum weighted independence number of a graph $G$ can be found by maximizing a linear objective function over the solution set of a particular LCP, denoted as $LCP(A+I, -e)$. Here, $A$ is the adjacency matrix of the graph, $I$ is the identity matrix, and $e$ is a vector of ones. This is a significant contribution as it connects a discrete graph problem to a continuous optimization framework.
For the independent domination number, they establish a relationship between its size and the minimum $l_1$ norm of solutions to the same LCP. They prove that this relationship is an equality for a specific class of graphs called forests (graphs that are a collection of trees).
The paper also delves into the properties of the solutions to these LCPs, particularly focusing on integer solutions. They demonstrate that integer solutions to $LCP(A+I, -e)$ correspond precisely to the characteristic vectors of maximal independent sets of the graph. This connection is crucial for understanding the relationship between LCP solutions and graph structures.
Furthermore, the authors explore applications of their LCP formulation, including deriving a new characterization for well-covered graphs (graphs where all maximal independent sets have the same size) and providing a stronger variant of the Lovász theta function, a well-known upper bound for the independence number. They also discuss the complexity implications of their findings, showing that their formulation leads to an NP-hard problem for approximating linear programs with complementarity constraints (LPCCs).
Datasets
Not discussed in the paper. The paper focuses on theoretical graph properties and their formulation using LCPs, rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- LCP as a Unified Framework: The paper elegantly unifies the study of weighted independence number and independent domination number under the umbrella of linear complementarity problems. This provides a fresh perspective and opens doors for applying LCP theory to graph problems.
- Integer Solutions as Maximal Independent Sets: The crucial insight that integer solutions to $LCP(A+I, -e)$ directly correspond to characteristic vectors of maximal independent sets is a cornerstone of their work. This connection simplifies the analysis of these graph structures.
- Tight Bound for Forests: The discovery that the minimum $l_1$ norm of LCP solutions equals the independent domination number specifically for forests is a significant theoretical result. It highlights a special property of tree-like graph structures within this LCP framework.
- New Lovász Theta Variant: The paper introduces a novel variant of the Lovász theta function, which is shown to be a tighter upper bound for the independence number than existing ones. This is achieved by leveraging the LCP formulation and semidefinite programming relaxations.
- LPCC Hardness: The reduction of the independence number problem to an LPCC demonstrates that LPCCs are hard to approximate, even for binary data, which has implications for the broader field of optimization.
Key Results
- Theorem 1: The weighted independence number of a graph $G$ is equal to the maximum $l_1$ norm of solutions to $LCP(A+I, -e)$, where $A$ is the adjacency matrix of $G$.
- Theorem 2: For a forest $G$, the independent domination number $\beta(G)$ is equal to the minimum $l_1$ norm of solutions to $LCP(A+I, -e)$.
- Lemma 4: Integer solutions to $LCP(A+I, -e)$ are precisely the characteristic vectors of maximal independent sets of $G$.
- New Lovász Theta Variant: The paper defines and analyzes a new variant of the Lovász theta function, denoted $\vartheta^*(G)$, which is shown to be a stronger upper bound for the independence number than the standard Lovász theta $\vartheta(G)$.
- Well-Covered Graphs: A new sufficient condition for a graph to be well-covered is derived based on the constancy of the $l_1$ norm over the solution set of $LCP(A+I, -e)$. This condition is also shown to be necessary for forests.
Limitations and Future Work
- General Graphs for Independent Domination: While the LCP formulation provides a lower bound for the independent domination number in general graphs, the equality only holds for forests. The gap between this lower bound and the actual independent domination number for general graphs is an area for further investigation.
- Computational Complexity: While the LCP formulation offers theoretical elegance, the practical computational efficiency for large, general graphs might still be a challenge, as LCPs themselves can be computationally intensive.
- LPCC Approximation: The paper establishes the hardness of approximating LPCCs. Future work could explore specific classes of LPCCs for which more efficient approximation algorithms might exist.
- Comparison of Lovász Theta Variants: The paper notes that while simulations suggest a hierarchy among different Lovász theta variants, direct theoretical comparisons between all variants (e.g., N+(FRAC(G)) and TH*(G)) remain an open problem.
Summary updated