Chromatic, flow and reliability polynomials: The complexity of their coefficients. (English) Zbl 1001.05034

Oxley, James; Welsh, Dominic

Comb. Probab. Comput. 11, No. 4, 403-426 (2002).

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