Computing the Tutte polynomial in vertexexponential time
(2008) 49th Annual Symposium on Foundations of Computer Science In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science p.677686 Abstract
 The deletioncontraction 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 FortuinKasteleyn in statistical physics. Prior to this work, deletioncontraction was also the fastest known generalpurpose 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 polynomialand hence, all the aforementioned invariants and moreof an arbitrary graph in time within a... (More)
 The deletioncontraction 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 FortuinKasteleyn in statistical physics. Prior to this work, deletioncontraction was also the fastest known generalpurpose 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 polynomialand hence, all the aforementioned invariants and moreof 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 polynomialspace 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:
http://lup.lub.lu.se/record/1376011
 author
 Björklund, Andreas ^{LU} ; Husfeldt, Thore ^{LU} ; Kaski, Petteri and Koivisto, Mikko
 organization
 publishing date
 2008
 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
 IEEEInstitute of Electrical and Electronics Engineers Inc.
 conference name
 49th Annual Symposium on Foundations of Computer Science
 external identifiers

 wos:000262484800068
 scopus:57949113843
 ISSN
 02725428
 DOI
 10.1109/FOCS.2008.40
 project
 Exact algorithms
 language
 English
 LU publication?
 yes
 id
 17fb22d9b2834a4b8bc22b820ef32144 (old id 1376011)
 date added to LUP
 20090417 09:24:05
 date last changed
 20180211 03:36:35
@inproceedings{17fb22d9b2834a4b8bc22b820ef32144, abstract = {The deletioncontraction 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 FortuinKasteleyn in statistical physics. Prior to this work, deletioncontraction was also the fastest known generalpurpose 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 polynomialand hence, all the aforementioned invariants and moreof 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 polynomialspace 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 = {02725428}, language = {eng}, pages = {677686}, publisher = {IEEEInstitute of Electrical and Electronics Engineers Inc.}, title = {Computing the Tutte polynomial in vertexexponential time}, url = {http://dx.doi.org/10.1109/FOCS.2008.40}, year = {2008}, }