patternMinor
Heuristic for weighted maximum independent set in graph with ~$2 \times 10^5$ nodes and $|E| \propto |V|$
Viewed 0 times
nodesmaximumgraphindependentwithweightedproptoheuristicforand
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#37940, answer score: 5
Revisions (0)
No revisions yet.