A graph polynomial for independent sets of bipartite graphs

Details A graph polynomial for independent sets of bipartite graphs A graph polynomial for independent sets of bipartite graphs

2009-11-24

arxiv.org/abs/0911.4732v4

Computer Science

Discrete Mathematics

Scientific paper

We introduce a new graph polynomial that encodes interesting properties of graphs, for example, the number of matchings and the number of perfect matchings. Most importantly, for bipartite graphs the polynomial encodes the number of independent sets (#BIS). We analyze the complexity of exact evaluation of the polynomial at rational points and show that for most points exact evaluation is #P-hard (assuming the generalized Riemann hypothesis) and for the rest of the points exact evaluation is trivial. We conjecture that a natural Markov chain can be used to approximately evaluate the polynomial for a range of parameters. The conjecture, if true, would imply an approximate counting algorithm for #BIS, a problem shown, by [Dyer et al. 2004], to be complete (with respect to, so called, AP-reductions) for a rich logically defined sub-class of #P. We give a mild support for our conjecture by proving that the Markov chain is rapidly mixing on trees. As a by-product we show that the "single bond flip" Markov chain for the random cluster model is rapidly mixing on constant tree-width graphs.

Affiliated with

Also associated with

No associations

Rating

A graph polynomial for independent sets of bipartite graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A graph polynomial for independent sets of bipartite graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A graph polynomial for independent sets of bipartite graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-622572