2002/07/01 by James Oxley, Dominic Welsh · 35 citations
Mathematics · Computer Science · #Advanced Combinatorial Mathematics #Graph theory and applications #Advanced Graph Theory Research #Chromatic polynomial #Mathematics #Chromatic scale #Tutte polynomial #Invariant (physics) #Combinatorics #Discrete mathematics #Polynomial #Flow (mathematics) #Graph #Mathematical analysis #Line graph #Voltage graph
paper · doi:10.1017/s0963548302005175
published in Combinatorics Probability Computing 11(4), 403-426 (Cambridge University Press)
openalex publication_date 2002/07/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
We study the complexity of computing the coefficients of three classical polynomials, namely the chromatic, flow and reliability polynomials of a graph. Each of these is a specialization of the Tutte polynomial Σ t ij x i y j . It is shown that, unless NP = RP , many of the relevant coefficients do not even have good randomized approximation schemes. We consider the quasi-order induced by approximation reducibility and highlight the pivotal position of the coefficient t 10 = t 01 , otherwise known as the beta invariant. Our nonapproximability results are obtained by showing that various decision problems based on the coefficients are NP -hard. A study of such predicates shows a significant difference between the case of graphs, where, by Robertson–Seymour theory, they are computable in polynomial time, and the case of matrices over finite fields, where they are shown to be NP -hard.