# 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)

##### MSC:
 05B35 Combinatorial aspects of matroids and geometric lattices 05C15 Coloring of graphs and hypergraphs 03D15 Complexity of computation (including implicit computational complexity)
##### Keywords:
matroid; graph; Tutte polynomial; complexity
Full Text: