Computing the Tutte Polynomial in Vertex-Exponential Time

Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto

    Publikation: Konference artikel i Proceeding eller bog/rapport kapitelKonferencebidrag i proceedingsForskningpeer review

    Abstract

    The deletion–contraction algorithm is perhapsthe 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.
    OriginalsprogEngelsk
    Titel2008 IEEE 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS)
    ForlagIEEE Press
    Publikationsdato2008
    Sider677-686
    ISBN (Trykt)978-0-7695-34367
    DOI
    StatusUdgivet - 2008
    Begivenhed2008 IEEE 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS) - Philadelphia, PA, USA
    Varighed: 25 okt. 200828 okt. 2008
    Konferencens nummer: 49

    Konference

    Konference2008 IEEE 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS)
    Nummer49
    Land/OmrådeUSA
    ByPhiladelphia, PA
    Periode25/10/200828/10/2008

    Emneord

    • Graph Theory
    • Tutte Polynomial
    • Algorithm Efficiency
    • Multivariate Polynomial
    • Fortuin-Kasteleyn Identity
    • Deletion-Contraction Algorithm
    • Chromatic Polynomial
    • Statistical Physics Models
    • Polynomial Space Algorithm
    • Cover Polynomial

    Citationsformater