<p>Let $G$ be an edge-weighted graph, and let (S, V-S) be a <em>feasible pair</em> 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. </p>

<p>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). </p>

<p>I know that there's a fair bit of study of sampling over independent sets (for example, <a href="http://portal.acm.org/citation.cfm?id=338615">this</a>). My question is:</p>

<blockquote>
  <p>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  ?</p>
</blockquote>

CC BY-SA 2.5
2011-02-21T08:17:18.910Z
I guess you intended to add a link to some paper at "(for example, this)".
Martin Schwarz
CC BY-SA 2.5
2011-02-22T02:22:11.573Z
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: http://www.springerlink.com/content/x708660058t38k38/
dan_x
<ds.algorithms><graph-algorithms><heuristics>
Good MCMC methods for exploring the space of independent sets
Suresh Venkat
# Good MCMC methods for exploring the space of independent sets

(Asked by: username_0 on 2011-02-21)

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](http://portal.acm.org/citation.cfm?id=338615)). 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 ?

**Tags:** ds.algorithms, graph-algorithms, heuristics
> **Comments:**
> **username_1**: I guess you intended to add a link to some paper at "(for example, this)".  
> **username_2**: 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: http://www.springerlink.com/content/x708660058t38k38/  

---

## 0 answers

