Authors: Parthe Pandit and Ankur A. Kulkarni
Abstract
This paper establishes a bridge between discrete graph theory and continuous optimization by leveraging the framework of Linear Complementarity Problems (LCPs). The authors provide exact continuous characterizations for the weighted independence number and the independent domination number, leading to tighter semidefinite programming (SDP) bounds and new hardness results for complementarity-constrained optimization.
Introduction
In graph theory, finding the maximum independent set—a set of vertices where no two are connected—is a classic NP-complete problem. The size of this set, the independence number $\alpha(G)$, and the related independent domination number $\beta(G)$ (the size of the smallest maximal independent set) are fundamental invariants. While continuous formulations like the Motzkin-Strauss theorem exist, they often struggle with weighted vertices or fail to capture the "maximality" required for domination numbers. This work introduces a unified continuous optimization framework based on Linear Complementarity Problems (LCPs) to address these limitations.
The LCP Framework
The core methodology involves mapping maximal independent sets to the solution set of an LCP. Given a graph with adjacency matrix $A$, the authors define $M = A + I$ and $q = -e$ (a vector of ones). They prove that the characteristic vectors of maximal independent sets are exactly the integer solutions to the LCP defined by:
- $x \ge 0$
- $y = Mx + q \ge 0$
- $x^\top y = 0$
This complementarity condition $x_i y_i = 0$ perfectly encodes the logic of a maximal independent set: either a vertex is in the set ($x_i=1$), or it must be "covered" by a neighbor ($y_i \ge 0$).
Hardness of LPCCs
A significant theoretical contribution of the paper is the reduction of the maximum independent set problem to a Linear Program with Complementarity Constraints (LPCC).
By showing that $\alpha(G)$ can be computed by maximizing a linear function over an LCP solution set, the authors provide a formal proof that LPCCs are NP-hard to approximate within a factor of $n^{1-\epsilon}$. This result highlights the inherent computational difficulty of this class of optimization problems.
Key Results and Bounds
The paper establishes several exactness results:
- Weighted Independence Number: For any graph and non-negative weights, $\alpha_w(G)$ is exactly the maximum weighted $\ell_1$ norm over the LCP solution set.
- Independent Domination in Forests: For forests, $\beta(G)$ is exactly the minimum $\ell_1$ norm over the LCP solution set. While this value can be fractional in general graphs, it aligns perfectly with the discrete value in acyclic structures.
To make these findings computationally useful, the authors derive a new semidefinite programming (SDP) bound, $\vartheta^*(G)$, using Lovász-Schrijver "lift-and-project" techniques. Numerical simulations on Erdős–Rényi random graphs $G(n, p)$ consistently show that $\vartheta^*(G)$ provides a tighter upper bound on $\alpha(G)$ than both the standard Lovász theta function ($\vartheta$) and the common $\vartheta'$ variant.
Conclusion
By framing discrete graph properties within the continuous LCP framework, Pandit and Kulkarni offer new insights into the structural properties of graphs and the complexity of complementarity constraints. Their proposed SDP bound $\vartheta^*$ represents a meaningful improvement in the ability to approximate the independence number of complex networks.
Summary updated