Hostname: page-component-74656f9884-npj9w Total loading time: 0 Render date: 2026-11-10T07:32:33.593Z Has data issue: false hasContentIssue false

Approximating the Number of Acyclic Orientations for a Class of Sparse Graphs

Published online by Cambridge University Press:  19 January 2004

MAGNUS BORDEWICH
Affiliation:
New College, Oxford OX1 3BN, UK Mathematical Institute, 24–29 St. Giles', Oxford OX1 3LB, UK (e-mail: bordewic@maths.ox.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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 [8] 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 randomized 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)$.

Information

Type
Paper
Copyright
© 2004 Cambridge University Press