Chromatic, flow and reliability polynomials: The complexity of their coefficients.

*(English)*Zbl 1001.05034The 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)