Advanced

Computing the Tutte polynomial in vertex-exponential time

Björklund, Andreas LU ; Husfeldt, Thore LU ; Kaski, Petteri and Koivisto, Mikko (2008) 49th Annual Symposium on Foundations of Computer Science In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science p.677-686
Abstract
The deletion-contraction algorithm is perhaps the most popular method for computing a host of fundamental graph invariants such as the chromatic, flow, and reliability polynomials in graph theory, the Jones polynomial of an alternating link in knot theory, and the partition functions of the models of Ising, Potts, and Fortuin-Kasteleyn in statistical physics. Prior to this work, deletion-contraction was also the fastest known general-purpose algorithm for these invariants, running in time roughly proportional to the number of spanning trees in the input graph. Here, we give a substantially faster algorithm that computes the Tutte polynomial-and hence, all the aforementioned invariants and more-of an arbitrary graph in time within a... (More)
The deletion-contraction algorithm is perhaps the most popular method for computing a host of fundamental graph invariants such as the chromatic, flow, and reliability polynomials in graph theory, the Jones polynomial of an alternating link in knot theory, and the partition functions of the models of Ising, Potts, and Fortuin-Kasteleyn in statistical physics. Prior to this work, deletion-contraction was also the fastest known general-purpose algorithm for these invariants, running in time roughly proportional to the number of spanning trees in the input graph. Here, we give a substantially faster algorithm that computes the Tutte polynomial-and hence, all the aforementioned invariants and more-of an arbitrary graph in time within a polynomial factor of the number of connected vertex sets. The algorithm actually evaluates a multivariate generalization of the Tutte polynomial by making use of an identity due to Fortuin and Kasteleyn. We also provide a polynomial-space variant of the algorithm and give an analogous result for Chung and Graham's cover polynomial. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
in
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science
pages
677 - 686
publisher
IEEE--Institute of Electrical and Electronics Engineers Inc.
conference name
49th Annual Symposium on Foundations of Computer Science
external identifiers
  • wos:000262484800068
  • scopus:57949113843
ISSN
0272-5428
DOI
10.1109/FOCS.2008.40
project
Exact algorithms
language
English
LU publication?
yes
id
17fb22d9-b283-4a4b-8bc2-2b820ef32144 (old id 1376011)
date added to LUP
2009-04-17 09:24:05
date last changed
2017-08-27 04:30:14
@inproceedings{17fb22d9-b283-4a4b-8bc2-2b820ef32144,
  abstract     = {The deletion-contraction algorithm is perhaps the most popular method for computing a host of fundamental graph invariants such as the chromatic, flow, and reliability polynomials in graph theory, the Jones polynomial of an alternating link in knot theory, and the partition functions of the models of Ising, Potts, and Fortuin-Kasteleyn in statistical physics. Prior to this work, deletion-contraction was also the fastest known general-purpose algorithm for these invariants, running in time roughly proportional to the number of spanning trees in the input graph. Here, we give a substantially faster algorithm that computes the Tutte polynomial-and hence, all the aforementioned invariants and more-of an arbitrary graph in time within a polynomial factor of the number of connected vertex sets. The algorithm actually evaluates a multivariate generalization of the Tutte polynomial by making use of an identity due to Fortuin and Kasteleyn. We also provide a polynomial-space variant of the algorithm and give an analogous result for Chung and Graham's cover polynomial.},
  author       = {Björklund, Andreas and Husfeldt, Thore and Kaski, Petteri and Koivisto, Mikko},
  booktitle    = {Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science},
  issn         = {0272-5428},
  language     = {eng},
  pages        = {677--686},
  publisher    = {IEEE--Institute of Electrical and Electronics Engineers Inc.},
  title        = {Computing the Tutte polynomial in vertex-exponential time},
  url          = {http://dx.doi.org/10.1109/FOCS.2008.40},
  year         = {2008},
}