2024-01-18
Approximating the chromatic polynomial is as hard as computing it exactly
Publication
Publication
Computational Complexity , Volume 33 p. 1:1- 1:47
We show that for any non-real algebraic number q, such that |q − 1| > 1 or (q) > 3 2 it is #P-hard to compute a multiplicative (resp. additive) approximation to the absolute value (resp. argument) of the chromatic polynomial evaluated at q on planar graphs. This implies #P-hardness for all non-real algebraic q on the family of all graphs. We, moreover, prove several hardness results for q, such that |q − 1| ≤ 1. Our hardness results are obtained by showing that a polynomial time algorithm for approximately computing the chromatic polynomial of a planar graph at non-real algebraic q (satisfying some properties) leads to a polynomial time algorithm for exactly computing it, which is known to be hard by a result of Vertigan. Many of our results extend in fact to the more general partition function of the random cluster model, a well-known reparametrization of the Tutte polynomial.
| Additional Metadata | |
|---|---|
| , , , , | |
| doi.org/10.1007/s00037-023-00247-8 | |
| Computational Complexity | |
| Organisation | Networks and Optimization |
|
Bencs, F., Huijben, J., & Regts, G. (2024). Approximating the chromatic polynomial is as hard as computing it exactly. Computational Complexity, 33, 1:1–1:47. doi:10.1007/s00037-023-00247-8 |
|
