The complexity of counting problems

Thesis

This thesis is concerned with the computational complexity of several counting problems occurring in graph theory, all of which are related directly to the Tutte polynomial. The Tutte polynomial contains as specialisations many fundamental quantities. Among these are the partition function of the Ising and Potts models on the graph and the reliability probability as well as basic combinatorial functions such as the chromatic and flow polynomials.

Polynomial-time computable recurrence relations are given for the Tutte polynomial of the complete graphs and complete bipartite graphs, which can be solved at certain points. The flow polynomials of a particular family of cubic graphs are shown to have arbitrarily large zeros, in contrast to the conjectured behaviour of the zeros of the chromatic and reliability polynomials.

The main results of the thesis are the following:

Theorem: For any positive (constant) integers i, j and k, computing the coefficient of xⁱ yⁱ in the Tutte polynomial of an arbitrary graph is #P-complete. However, it can be checked in polynomial time whether the coefficient is less than k.

The complexity of evaluating the Tutte polynomial modulo a prime is also considered, and some partial results are given.

Turning to approximation, a polynomial-time uniform generator for forests of dense graphs is given. Using this, a fully polynomial randomised approximation scheme (fpras) for the number of forests of a dense graph is created. This leads to the following generalisation:

Theorem: For any rational x ≥ 1, there exists a fully polynomial randomised approximation scheme for evaluating the Tutte polynomial of dense graphs at the point (x,1).

Authors: Annan, J; Annan, James

• Publication date: 1994
• DOI: 10.5287/ora-w4pvnnme4
• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Language: English
• Subjects: Research; Graph theory