License
when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2010.240
URN: urn:nbn:de:0030-drops-28676
URL: http://drops.dagstuhl.de/opus/volltexte/2010/2867/
Ge, Qi ; Stefankovic, Daniel

A graph polynomial for independent sets of bipartite graphs

pdf-format:
Dokument 1.pdf (483 KB)

Abstract

We introduce a new graph polynomial that encodes interesting properties of graphs, for example, the number of matchings, the number of perfect matchings, and, for bipartite graphs, the number of independent sets (#BIS). We analyze the complexity of exact evaluation of the polynomial at rational points and show a dichotomy result---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 propose a natural Markov chain to approximately evaluate the polynomial for a range of parameters. We prove an upper bound on the mixing time of the Markov chain 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.

BibTeX - Entry

@InProceedings{ge_et_al:LIPIcs:2010:2867,
  author =	{Qi Ge and Daniel Stefankovic},
  title =	{{A graph polynomial for independent sets of bipartite graphs}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)},
  pages =	{240--250},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-23-1},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{8},
  editor =	{Kamal Lodaya and Meena Mahajan},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2867},
  URN =		{urn:nbn:de:0030-drops-28676},
  doi =		{http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2010.240},
  annote =	{Keywords: graph polynomials, #P-complete, independent sets, approximate counting problems, Markov chain Monte Carlo}
}

Keywords: graph polynomials, #P-complete, independent sets, approximate counting problems, Markov chain Monte Carlo
Seminar: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)
Issue date: 2010
Date of publication: 14.12.2010

DROPS-Home | Fulltext Search | Imprint Published by LZI