# Heuristic for weighted maximum independent set in graph with ~$2 \times 10^5$ nodes and $|E| \propto |V|$

I want to find a near-optimal solution for a maximum weight independent set. i.e given a graph $G = (V,E)$ I want to find a set $S = \{v_1,v_2,\dots,v_n\}$ of nodes in $V$ such that the sum of their weights is maximum (The weights are positive), under the constraint that every pair is not connected by an edge, i.e $\forall\ v_i,v_j \in S:(v_i,v_j) \not\in E$.

A common problem instance would be a graph with around $2 \times 10^5$ nodes, up to around $5 \times 10^5$. The degree of a node is bounded by ~$100$, and the number of edges will be around $10^6$.

Can anyone recommend a heuristic algorithm for finding a near-optimal solution? A runtime of hours or even days is acceptable.

I've been looking so far at articles about Tabu search and that is the current direction I am going towards.

• Do the costs of the nodes follow some distribution? In other words, is there any thing that could be exploited? (e.g., is the graph sparse or fully connected?) Another question: what do you mean by "near-optimal"? If brute-force is the only approach for solving the problem optimally, the suboptimality ratio might be simply unknown for graphs with $\sim 10^5$. A last question: have you looked at linear programming tasks? Maybe this has been considered previously there Feb 5, 2015 at 23:01
• By near-optimal I just meant to use a heuristic, I don't expect a certain bound on the approximation ratio. The graph is sparse (this means $|E| \propto |V|$ as far as I know.) The weight distribution should be approximately uniform on an interval $[-1,1]$. About linear programming, I am not sure how this would be modelled in that way. I thought about integer programming where each vertex is represented by a binary variable which indicates whether it's included in a solution or not. But as far as I know, integer programming would not handle such a large problem, though I will try that as well. Feb 6, 2015 at 1:17