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.
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)