Skip to main content

Research Repository

Advanced Search

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

Bordewich, M.

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


Authors



Abstract

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)$.

Citation

Bordewich, M. (2004). Approximating the number of acyclic orientations for a class of sparse graphs. Combinatorics, Probability and Computing, 13(1), 1-16. https://doi.org/10.1017/s0963548303005844

Journal Article Type Article
Publication Date 2004-01
Deposit Date Jun 18, 2008
Publicly Available Date Mar 29, 2024
Journal Combinatorics, Probability and Computing
Print ISSN 0963-5483
Electronic ISSN 1469-2163
Publisher Cambridge University Press
Peer Reviewed Peer Reviewed
Volume 13
Issue 1
Pages 1-16
DOI https://doi.org/10.1017/s0963548303005844
Keywords Tutte polynomial, FPRAS, Approximation, Complexity.

Files

Published Journal Article (156 Kb)
PDF

Copyright Statement
© 2004 Cambridge University Press





You might also like



Downloadable Citations