The Tutte polynomial of a graph G is a two-variable polynomial that encodes many interesting properties of the graph. For example, if you evaluate the polynomial at the point (1,1) the result is the number of spanning trees of the graph. If you evaluate the polynomial at the point (-2,0), you get the number of 3-colourings of the graph.

The complexity of exactly evaluating the Tutte polynomial of a graph is mostly understood - the problem can be solved in polynomial time if the point (x,y) is one of the four "special points" (1,1), (0,-1), (-1,0) and (-1,-1). It can also be solved in polynomial time if (x,y) is on the hyperbola (x-1)(y-1)=1. At any other point (x,y) it is difficult to evaluate the Tutte polynomial in the sense that this problem is complete for the complexity class #P.

We are also interested in the complexity of approximately evaluating the Tutte polynomial. See the paper

• L.A. Goldberg and M. Jerrum, Inapproximability of the Tutte polynomial

Within the region given by and , the way to show that the Tutte polynomial is inapproximable at a point $(x,y)$ is to reduce computation at a known hard point $(x\text{'},y\text{'})$ to computation at the point $(x,y)$. This is known as "shifting" $(x,y)$ to $(x\text{'},y\text{'})$.

The goal of this project is to write a program which implements shifting and to use it to explore the complexity of approximating the Tutte polynomial within the region given by and . Starting from known inapproximable points (listed in the paper above), you will use your program to discover new inapproximable points.

The goal is to map out the region given by and , determining for which points in the region the Tutte polynomial is inapproximable. It is unlikely that you will solve the whole region, so the goal is to find an inapproximable region which is as large as possible.

It is not necessary for the project to understand all of the proofs in the above paper, but you will need to be able understand the details of Sections 1-3 of the paper (including proofs). Section 4.1 may also be useful.

The purpose of this project is to produce some software for animating algorithms for finding matchings in graphs. A useful starting point would be the Hungarian algorithm (which finds a maximum matching in a bipartite graph). You can find a description of this algorithm in the notes for the module Efficient Sequential Algorithms (Comp309) See the module website http://www.csc.liv.ac.uk/~leslie/comp309/comp309index0910.html (go to the section on matchings). The project could be extended to implement other algorithms for finding matchings.

The project gives you the opportunity to expand on what you learned about randomised algorithms in ``advanced algorithmic techniques'' by implementing a brand-new randomised algorithm for sampling an independent set uniformly at random in a bipartite graph. The algorithm is described in http://arxiv.org/abs/0911.4732 I would recommend that you use a programming language such as mathematica or maple, because you will need a sub-routine for sampling uniformly at random from the set of solutions to a system of linear equations.