# Good MCMC methods for exploring the space of independent sets

Let $G$ be an edge-weighted graph, and let (S, V-S) be a feasible pair if S is a maximal independent set. The weight of a feasible pair is computed by finding for each element of V-S the lightest edge connecting it to S, and summing the costs (such an edge must exist since S maximal). The goal is to find a minimum weight pair.

This problem is NP-hard and is likely to be fairly hard to approximate (it encodes vertex cover at the very least). We're looking at heuristics that might be effective in practice, and one idea is to do some kind of metropolis-hastings-type walk on the space of all independent sets (since given an independent set, computing the weight is easy).

I know that there's a fair bit of study of sampling over independent sets (for example, this). My question is:

Are there good sampling procedures that can be adapted to this weighted case ? I suspect I'd like some kind of procedure that does a metropolis-hastings-type step to decide whether to move or not, and so the question really is: what are good local moves ?

• I guess you intended to add a link to some paper at "(for example, this)". – Martin Schwarz Feb 21 '11 at 8:17
• It's not quite the same problem, but this paper dicusses "chain flipping" MCMC proposals for weighted bipartite matching problems. It could be relevant as inspiration: springerlink.com/content/x708660058t38k38 – dan_x Feb 22 '11 at 2:22