文章基本信息

标题：A graph polynomial for independent sets of bipartite graphs
本地全文：下载
作者：Qi Ge ; Daniel Stefankovic
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2010
卷号：8
页码：240-250
DOI：10.4230/LIPIcs.FSTTCS.2010.240
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：graph polynomials; #P-complete; independent sets; approximate counting problems; Markov chain Monte Carlo