The Computational Complexity of Tutte Invariants for Planar Graphs

DOI10.1137/S0097539704446797MaRDI QIDQ5470709zbMATH OpenOpenAlexWikidataFDO

Authors Dirk Vertigan

Publication date 1 June 2006

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539704446797

zbMATH Keywords

\(\#P\)-completeenumerationknot polynomialspercolationplanar graphspolynomial timePotts modelreliabilityTutte polynomial

Mathematics Subject Classification ID

Combinatorial identities, bijective combinatorics (05A19) Combinatorial aspects of matroids and geometric lattices (05B35) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Graph theory (including graph drawing) in computer science (68R10) Percolation (82B43)

Recommendations

• The exact complexity of the Tutte polynomial
• The computational complexity of knot and matroid polynomials
• Inapproximability of the Tutte polynomial of a planar graph
• The Computational Complexity of the Tutte Plane: the Bipartite Case
• Computing the Tutte polynomial of a graph of moderate size

Cited in

(41)

• Combinatorial aspects of network reliability
• The computational complexity of knot and matroid polynomials
• Network reliability and the probabilistic estimation of damage from fire spread
• The complexities of the coefficients of the Tutte polynomial
• The Tutte polynomial modulo a prime
• An algorithm for the Tutte polynomials of graphs of bounded treewidth
• Sixty years of network reliability
• The complexity of computing the Tutte polynomial on transversal matroids
• A new approach to solving three combinatorial enumeration problems on planar graphs
• Inapproximability of the Tutte polynomial of a planar graph
• Interpretations of the Tutte and characteristic polynomials of matroids
• FKT is not universal -- a planar holant dichotomy for symmetric constraints
• The complexity of approximating the complex-valued Potts model
• A computational complexity comparative study of graph tessellation problems
• Interpretations of the Tutte polynomials of regular matroids
• Complexity dichotomy for oriented homomorphism of planar graphs with large girth
• Edge cut splitting formulas for Tutte-Grothendieck invariants
• A dichotomy for real weighted Holant problems
• Computing the Tutte polynomial of Archimedean tilings
• Coloring planar graphs via colored paths in the associahedra
• Complexity of Ising polynomials
• A graph integral formulation of the circuit partition polynomial
• The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems
• Complexity of graph polynomials
• Graph parameters from symplectic group invariants
• The Computational Complexity of the Tutte Plane: the Bipartite Case
• The complexity of approximating the complex-valued Potts model
• Modifications of Tutte-Grothendieck invariants and Tutte polynomials
• A parity result of Fraysseix, computational complexity of Tutte polynomials, and a conjecture on planar graphs
• The exact complexity of the Tutte polynomial
• Approximating the chromatic polynomial is as hard as computing it exactly
• On the number of \(k\)-proper connected edge and vertex colorings of graphs
• Computing the Tutte polynomial of a graph of moderate size
• The complexity of counting planar graph homomorphisms of domain size 3
• Tutte polynomials computable in polynomial time
• Dirac traces and the Tutte polynomial
• A coarse Tutte polynomial for hypermaps
• Complexity classes as mathematical axioms
• Planar graph coloring is not self-reducible, assuming P\(\neq NP\)
• Network reliability: Numbers or insight? (A discussion paper)
• A little statistical mechanics for the graph theorist

This page was built for publication: The Computational Complexity of Tutte Invariants for Planar Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5470709)