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 ?

  • $\begingroup$ I guess you intended to add a link to some paper at "(for example, this)". $\endgroup$ Feb 21, 2011 at 8:17
  • 1
    $\begingroup$ 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 $\endgroup$
    – dan_x
    Feb 22, 2011 at 2:22


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.