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.