A MWIS of a set of vertices in a graph is a subset in wich no two vertices are adjacent (that's an independent set) and such that the sum of the vertices weight is maximal among all independent sets.
Let p be a path in an undirected graph (in wich no vertex appears twice). We obtain the maximum weight for an independent set of p using dynamic programming by computing the maximum weight for sub-paths of p. Sub-paths are obtained adding vertices one at a time, in their order of appearance in p.
Once the maximum weights are known for all such sub-paths, the list of vertices composing the MWIS for p can be retrieved by browsing the list of maximum weights backwards.
Thus computing the maximum weight for an independent set of p and retrieving the corresponding MWIS is performed with linear complexity.
When not restricting to a path (see above), the problem of finding a maximum weight independent set in a graph is NP-hard, so approximation algorithms are provided here.
For a vertex v in the graph, let's denote by W(v) and d(v) the weight and the degree of v in the graph. Then alpha, the sum over the vertices v of W(v)/(d(v) + 1) is a minorant for the weight of a maximum weight independent set.
The two greedy algorithms implemented are based on algorithms GWMIN and GWMAX described in this article. They both return in any case an independent set whose weight is greater than alpha.
To build the executable, run in the source folder:
mkdir bin && cd src/ && make && cd ..Toy around with a few examples using:
./bin/mwis -pSee main file to modify graph and paths used in the examples.
Use:
./bin/mwis -g sizeto build a random graph with size vertices and log the result of
the two algorithms on this graph.