Journal article

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

Abstract:

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 ∑tijxiyj. 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 t10 = t01, otherwise known as th...

Publication status:
Published

Access Document

Publisher copy:
10.1017/S0963548302005175

Authors

Journal:
COMBINATORICS PROBABILITY and COMPUTING
Volume:
11
Issue:
4
Pages:
403-426
Publication date:
2002-07-05
DOI:
EISSN:
1469-2163
ISSN:
0963-5483
URN:
uuid:ac77448c-7227-4b4f-aa2f-f6098a26a1ca
Source identifiers:
17243
Local pid:
pubs:17243
Language:
English