Login
Computer Science @ Rochester
Tuesday, December 06, 2011
10:00 AM
Computer Science Bldg. Room 703
Qi Ge
University of Rochester
Exact and Approximate Counting of Graph Objects: Independent Sets, Eulerian Tours, and More
Counting problems are fundamental in a variety of areas. For example, enumerative combinatorics, statistics, statistical physics, and artificial intelligence.

In this dissertation, we investigate several counting problems, which are subjects of active research. The specific problems considered are: counting independent sets in bipartite graphs (#BIS), computing the partition function of the hard-core model (Hardcore($\lambda$)), counting Eulerian tours (#ET), counting weighted matchings in bipartite graphs (#BipMatch) and related problems, and counting $q$-colorings (#$q$-Coloring). We study these problems from the viewpoint of exact counting, i.e., whether one can efficiently compute the answers exactly, as well as the viewpoint of approximability, i.e., whether one can efficiently compute the answers approximately.

To tackle #BIS, we create a new graph polynomial: the $R_2$ polynomial. The most interesting property of this polynomial is that it encodes the number of independent sets in bipartite graphs. We investigate properties of the $R_2$ polynomial, the computational complexity of exact evaluation of the polynomial at various points, and the problem of approximate evaluation of the polynomial.

For Hardcore($\lambda$), we extend Sly's results and almost resolve the computational complexity of approximating the partition function of the hard-core model on graphs of maximum degree $\Delta$. We prove for every $\Delta \geq 3$ except $\Delta \in \{4,5\}$, unless NP$=$RP, there does not exist an FPRAS for Hardcore($\lambda$) when $\lambda>\lambda_c(\Tree_{\Delta})$, where $\lambda_c(\Tree_{\Delta})$ is the threshold for the uniqueness of Gibbs measures on infinite $\Delta$-regular trees.

For #ET and its variation #A-trail, we prove #P-completeness results for the exact computation of #ET in $4$-regular graphs and #A-trail in $4$-regular maps. We also establish a reduction from the approximate computation of #ET in Eulerian graphs to the approximate computation of #A-trail in $4$-regular maps.

We explore applications of an FPRAS for #BipMatch and two related matching problems which generalize #BipMatch. We analyze properties of match-gates and develop an FPRAS for a variation of the ICE model using match-gates.

For #$q$-Coloring, we establish the strong spatial mixing of $q$-colorings on $(b+1)$-regular Bethe lattices, for $q \geq 1+\lceil 1.764b \rceil$. We also establish the strong spatial mixing of $q$-colorings on binary trees, for $q=4$.