Eastern Great Lakes Theory Workshop Talk

A graph polynomial for independent sets of bipartite graphs

Qi Ge, University of Rochester

Saturday, October 9, 5:00-5:30pm

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.

Slides

Speaker Bio

Qi Ge is a Ph.D. candidate, supervised by Prof. Daniel Stefankovic, in the theory group at UofR. His research interests focus on the design and analysis of efficient algorithms and computational complexity theory. He is now working on designing efficient (randomized) algorithms, especially by using Markov chain Monte Carlo methods, for counting problems (generally partition functions of weighted combinatorial structures), and the complexity (mainly with respect to approximability) of these counting problems. Qi received my B.S. and M.S. in Department of Computer Science and Engineering from Fudan University in 2003 and 2006, respectively.

< Schedule < EaGL-III homepage