> I would like to solve an instance of minimum set cover. Is there some > way to do this by formulating it the problem as a bipartite graph and > using igraph?
If you are looking for an exact solution, then the answer is probably no (although I'm not 100% sure). However, there exists a greedy algorithm for minimum set covers that achieves an approximation ratio of H(m) if there are m items to be covered [1]. This greedy algorithm is fairly easy to implement: 1. Construct a bipartite graph where the first N vertices represent the sets and the remaining M vertices represent the items to be covered. Connect an item to a set if the item is in the set. 2. If there are no vertices to be covered, you are done. 3. Choose the set (i.e. the vertex among the first N vertices) with the highest degree, add it to the cover and remove all its neighbors from the graph. 4. Go to step 2. You can also combine the above technique with a local search using simulated annealing or some other meta-heuristic, starting from the configuration given by the greedy algorithm. [1] http://www.jstor.org/stable/3689577 -- T. _______________________________________________ igraph-help mailing list [email protected] https://lists.nongnu.org/mailman/listinfo/igraph-help
