Heuristic to find the maximum weight independent set in an arbritary graph

Question

The MWIS (Maximum weight independent set) is a NP-complete problem, so if P!=NP we cannot find a solution in a good enough time complexity.

I am looking for an algorithm that can find an approximation of the MWIS in an arbitrary graph within a good time complexity. I am currently working on a connected graph with 128 nodes and 3051 edges.

I have found this paper, but it seems that it is only working for bipartite graph with an unique MWIS.

I will be glad if anyone can help me with some references or even better with a pseudo-code of a working algorithm.

Answer 1

It's possible to formulate this as the following problem. Suppose each vertex v in the graph has weight w(v). You define a variable x(v), and use some out-of-the-box linear programming solver to solve

max \sum_v w(v) x(v) (maximize the weight of chosen vertices)

subject to

x(u) + x(v) <= 1, (u, v) \in E (don't take neighbors)

and

x(v) \in {0, 1} (can only choose to take or not take a vertex)

---

This is a combinatorical problem (the last constraint is exponential in the number of vertices). There are two ways to continue from here:

• Switch the last constraint to

  x(v) \in [0, 1] (extent to which you choose a vertex)

  solve it with an LP solver, and continue along this paper, 4.3.

• In the comment below, David Eisenstat claims that for the sizes of your graph, an integer solver will do just fine (and yield better results)

Answer 2

To solve MWIS, you can use a a maximum weight clique solver on the complement graph. TSM-MWC is a fast algorithm implemented in C. If you graphs aren't too large, you may be able to solve the problem using Networkx in Python: here are reference pages for the complement and max_weight_clique functions.

Answer 3

Here is the code for finding a minimum weighted-degree vertex for MWIS, as suggested in the paper referenced by @Ami.

import networkx as nx
import numpy as np
graph = nx.generators.random_graphs.barabasi_albert_graph(50,10)
for u in graph:
    graph.nodes[u]['weight'] = np.random.uniform(0,1)

adj_0 = nx.adj_matrix(graph).todense()
a = -np.array([graph.nodes[u]['weight'] for u in graph.nodes])
IS = -np.ones(adj_0.shape[0])
while np.any(IS==-1):
    rem_vector = IS == -1
    adj = adj_0.copy()
    adj = adj[rem_vector, :]
    adj = adj[:, rem_vector]

    u = np.argmin(a[rem_vector].dot(adj!=0)/a[rem_vector])
    n_IS = -np.ones(adj.shape[0])
    n_IS[u] = 1
    neighbors = np.argwhere(adj[u,:]!=0)
    if neighbors.shape[0]:
        n_IS[neighbors] = 0
    IS[rem_vector] = n_IS
print IS

IS is the minimal weighted independent set.