Abstract
We investigate the question of tightness of linear programming (LP) relaxation for finding a maximum weight independent set (MWIS) in sparse random weighted graphs. We show that an edge-based LP relaxation is asymptotically tight for Erdos-Renyi graph $G(n,c/n)$ for $c \leq 2e$ and random regular graph $G(n,r)$ for $r\leq 4$ when node weights are i.i.d. with exponential distribution of mean 1. We establish these results, through a precise relation between the tightness of LP relaxation and convergence of the max-product belief propagation algorithm. We believe that this novel method of understanding structural properties of combinatorial problems through properties of iterative procedure such as the max-product should be of interest in its own right.
Introduction
The Maximum Weight Independent Set (MWIS) problem is a cornerstone of combinatorial optimization, requiring the selection of a set of nodes with maximum total weight such that no two selected nodes share an edge. Despite its broad utility in fields like computer vision and wireless networking, MWIS is notoriously NP-hard and difficult to approximate in the worst case.
A standard approach to tackle such problems is through Linear Programming (LP) relaxations. By relaxing the binary constraint (a node is either in or out) to a continuous one (a node is "partially" in), we gain the ability to solve the problem in polynomial time. However, these relaxations often yield fractional solutions that do not directly translate to a valid independent set. This research explores the conditions under which this simple LP relaxation is "tight"—meaning it yields the correct integer solution—specifically within the context of sparse random graphs.
Methods
The core innovation of this work lies in its unconventional proof technique: using the Max-product Belief Propagation (BP) algorithm as a lens to analyze LP tightness.
The BP-LP Link
The authors establish a formal correspondence between the convergence of Max-product BP and the integrality of the LP solution. Specifically, if the BP algorithm converges to a stable state for a given node, that node's corresponding value in the LP relaxation is guaranteed to be an integer (0 or 1). Conversely, fractional LP solutions manifest as oscillations or lack of convergence in the BP message-passing process.
Computation Trees
To analyze BP's behavior, the authors utilize the "computation tree" interpretation. In this view, the messages exchanged by BP at any time step $t$ are equivalent to an exact solution on a tree-structured graph that represents the local neighborhood of a node.
As shown in the figure above, the computation tree $T_a(t)$ unwinds the cycles of the original graph. This allows the researchers to leverage the fact that MWIS is easily solvable on trees to draw conclusions about the more complex original graph.
Local Weak Convergence
To generalize these findings to large random graphs, the "objective method" or local weak convergence is employed. This mathematical framework allows the analysis of BP on an infinite tree that serves as the "average" local structure of the random graph ensemble, facilitating proofs of asymptotic behavior.
Experimental Framework
The study focuses on two primary mathematical ensembles of random graphs with independent and identically distributed (i.i.d.) node weights drawn from an exponential distribution with mean 1:
- Erdos-Renyi Graphs $G(n, c/n)$: Where edges exist between any two nodes with probability $c/n$.
- Random Regular Graphs $G(n, r)$: Where every node has a fixed degree $r$.
Key Insights
- Algorithms as Proof Tools: The methodology flips the traditional paradigm. Instead of using LP theory to justify an algorithm, it uses the iterative behavior of BP to prove structural properties (tightness) of the LP.
- The Oscillation Signature: The paper identifies that fractional LP solutions are the root cause of non-convergence in Max-product BP. If the LP optimum is fractional (e.g., 0.5), the BP messages will oscillate indefinitely.
- Average-Case Tractability: While MWIS is hard in the worst case, the "locally tree-like" nature of sparse random graphs makes the problem effectively solvable via LP and BP with high probability.
Key Results
The research demonstrates that for Erdos-Renyi graphs with average degree $c \leq 2e$ (~5.43) and random regular graphs with degree $r \leq 4$, the LP relaxation is asymptotically tight for a $1 - o(1)$ fraction of nodes. This implies that for these specific graph classes, the MWIS problem can be solved efficiently in polynomial time. Furthermore, the Max-product BP algorithm is shown to converge to the correct MWIS values for almost all nodes, and the weight of the resulting independent set converges to the true maximum weight as the graph size increases.
Limitations and Future Work
While groundbreaking, the results are currently tied to the properties of the exponential weight distribution. Extending these proofs to other continuous distributions remains an open challenge. Additionally, the findings are restricted to sparse graphs; as graph density increases, long-range correlations disrupt the local tree-like structure, and the LP relaxation becomes less effective. Future research may apply this "iterative algorithm" approach to other combinatorial problems like vertex cover or matching.
Summary updated