We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Approximating the number of acyclic orientations for a class of sparse graphs.

Bordewich, M. (2004) 'Approximating the number of acyclic orientations for a class of sparse graphs.', Combinatorics, probability and computing., 13 (1). pp. 1-16.


The Tutte polynomial $T(G;x,y)$ of a graph evaluates to many interesting combinatorial quantities at various points in the $(x,y)$ plane, including the number of spanning trees, number of forests, number of acyclic orientations, the reliability polynomial, the partition function of the Q-state Potts model of a graph, and the Jones polynomial of an alternating link. The exact computation of $T(G;x,y)$ has been shown by Vertigan and Welsh \cite{vertiganandwelsh} to be \#P-hard at all but a few special points and on two hyperbolae, even in the restricted class of planar bipartite graphs. Attention has therefore been focused on approximation schemes. To date, positive results have been restricted to the upper half plane $y>1$, and most results have relied on a condition of sufficient denseness in the graph. In this paper we present an approach that yields a fully polynomial randomised approximation scheme for $T(G;x,y)$ for $x>1,\ y=1$, and for $T(G;2,0)$, in a class of sparse graphs. This is the first positive result that includes the important point $(2,0)$.

Item Type:Article
Keywords:Tutte polynomial, FPRAS, Approximation, Complexity.
Full text:(VoR) Version of Record
Download PDF
Publisher Web site:
Publisher statement:© 2004 Cambridge University Press
Date accepted:No date available
Date deposited:23 May 2008
Date of first online publication:January 2004
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar