5
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$
    – Carlos Linares López
    Feb 5, 2015 at 23:01
  • $\begingroup$ 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. $\endgroup$
    – fiftyeight
    Feb 6, 2015 at 1:17

1 Answer 1

Reset to default
5
$\begingroup$

Unfortunately, (weighted) maximum independent set is very hard to approximate. You might be able to do a bit better if you can analyze the graphs in your application (perhaps they are not truly arbitrary).

In any case, luckily your graphs are quite small (200 thousand vertices or so). A naive algorithm (say a greedy one) will run quite fast, but might be far from the optimum. Especially since several hours (or even days) of runtime is fine, I'd experiment with a genetic algorithm.

Being a rather central problem, there are studies into this as well. For a starter, one could look at [1]. In practice, I would expect one to be quite happy with such an approach.

[1] Hifi, Mhand. "A genetic algorithm-based heuristic for solving the weighted maximum independent set and some equivalent problems." Journal of the Operational Research Society 48.6 (1997): 612-622.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.