1 Search Results for "Ge, Qi"


Document
A graph polynomial for independent sets of bipartite graphs

Authors: Qi Ge and Daniel Stefankovic

Published in: LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)


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.

Cite as

Qi Ge and Daniel Stefankovic. A graph polynomial for independent sets of bipartite graphs. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 240-250, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{ge_et_al:LIPIcs.FSTTCS.2010.240,
  author =	{Ge, Qi and Stefankovic, Daniel},
  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 =	{Lodaya, Kamal and Mahajan, Meena},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.240},
  URN =		{urn:nbn:de:0030-drops-28676},
  doi =		{10.4230/LIPIcs.FSTTCS.2010.240},
  annote =	{Keywords: graph polynomials, #P-complete, independent sets, approximate counting problems, Markov chain Monte Carlo}
}
  • Refine by Author
  • 1 Ge, Qi
  • 1 Stefankovic, Daniel

  • Refine by Classification

  • Refine by Keyword
  • 1 #P-complete
  • 1 Markov chain Monte Carlo
  • 1 approximate counting problems
  • 1 graph polynomials
  • 1 independent sets

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2010

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail