zbMATH — the first resource for mathematics

Chromatic, flow and reliability polynomials: The complexity of their coefficients. (English) Zbl 1001.05034
The authors study the complexity of computing the coefficients of the chromatic, flow and reliability polynomials of a graph or more generally the coefficients of the Tutte polynomial \(\sum t_{ij} x^iy^j\) of a matroid with a succinct presentation. (In practice they consider matroids coordinatizable over a field.) It is shown that, unless NP = RP, for many of the relevant coefficients there do not even exist good randomized approximation schemes. They then consider the quasi-order induced by approximation reducibility where the beta invariant (\(t_{01}\)) has a pivotal position. The nonapproximability results are obtained by showing that various decision problems based on the coefficients are NP-hard. In particular they show that there are such predicates which are, from Robertson-Seymour theory, computable in polynomial time for graphs and NP-hard for matroids represented over finite fields.
Reviewer: D.L.Forge (Paris)

05B35 Combinatorial aspects of matroids and geometric lattices
05C15 Coloring of graphs and hypergraphs
03D15 Complexity of computation (including implicit computational complexity)
Full Text: DOI