{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T18:39:21Z","timestamp":1780079961842,"version":"3.54.0"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,1,18]],"date-time":"2024-01-18T00:00:00Z","timestamp":1705536000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,1,18]],"date-time":"2024-01-18T00:00:00Z","timestamp":1705536000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2024,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We show that for any non-real algebraic number <jats:italic>q<\/jats:italic>, such that\n<jats:inline-formula><jats:alternatives><jats:tex-math>$$|q-1|&gt;1$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>|<\/mml:mo>\n                    <mml:mi>q<\/mml:mi>\n                    <mml:mo>-<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>|<\/mml:mo>\n                    <mml:mo>&gt;<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> or <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\Re(q)&gt;\\frac{3}{2}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u211c<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>q<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:mo>&gt;<\/mml:mo>\n                    <mml:mfrac>\n                      <mml:mn>3<\/mml:mn>\n                      <mml:mn>2<\/mml:mn>\n                    <\/mml:mfrac>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> it is #P-hard to compute\na multiplicative (resp. additive) approximation to the absolute\nvalue (resp. argument) of the chromatic polynomial evaluated at <jats:italic>q<\/jats:italic> on planar graphs. This implies #P-hardness for all\nnon-real algebraic <jats:italic>q<\/jats:italic> on the family of all graphs. We, moreover,\nprove several hardness results for <jats:italic>q<\/jats:italic>, such that <jats:inline-formula><jats:alternatives><jats:tex-math>$$|q-1|\\leq 1$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>|<\/mml:mo>\n                    <mml:mi>q<\/mml:mi>\n                    <mml:mo>-<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>|<\/mml:mo>\n                    <mml:mo>\u2264<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p><jats:p>Our hardness results are obtained by showing that a polynomial time\nalgorithm for <jats:italic>approximately<\/jats:italic> computing the chromatic\npolynomial of a planar graph at non-real algebraic <jats:italic>q<\/jats:italic> (satisfying\nsome properties) leads to a polynomial time algorithm for\n<jats:italic>exactly<\/jats:italic> computing it, which is known to be hard by a result\nof Vertigan. Many of our results extend in fact to the more general\npartition function of the random cluster model, a well-known\nreparametrization of the Tutte polynomial.<\/jats:p>","DOI":"10.1007\/s00037-023-00247-8","type":"journal-article","created":{"date-parts":[[2024,1,18]],"date-time":"2024-01-18T16:02:26Z","timestamp":1705593746000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Approximating the chromatic polynomial is as hard as computing it exactly"],"prefix":"10.1007","volume":"33","author":[{"given":"Ferenc","family":"Bencs","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jeroen","family":"Huijben","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Guus","family":"Regts","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2024,1,18]]},"reference":[{"key":"247_CR1","doi-asserted-by":"crossref","unstructured":"Alexander Barvinok (2016). Combinatorics and complexity of partition functions, volume 30 of Algorithms and Combinatorics. Springer, Cham. ISBN 978-3-319-51828-2; 978-3-319-51829-9, vi+303 . URL \nhttps:\/\/doi-org.proxy.uba.uva.nl\/10.1007\/978-3-319-51829-9.","DOI":"10.1007\/978-3-319-51829-9"},{"key":"247_CR2","doi-asserted-by":"crossref","unstructured":"Ferenc Bencs, Jeroen Huijben & Guus Regts (2023). On the location of chromatic zeros of series-parallel graphs. Electron. J. Combin. 30(3), Paper No. 3.2, 22. ISSN 1077-8926. URL https:\/\/doi.org\/10.37236\/11204.","DOI":"10.37236\/11204"},{"key":"247_CR3","doi-asserted-by":"crossref","unstructured":"Ivona Bez\u00e1kov\u00e1, Andreas Galanis, Leslie Ann Goldberg & Daniel \u0160tefankovi\u010d (2020). Inapproximability of the independent set polynomial in the complex plane. SIAM J. Comput. 49(5), STOC18\u2013395\u2013STOC18\u2013448. ISSN 0097-5397. URL https:\/\/doi-org.proxy.uba.uva.nl\/10.1137\/18M1184485.","DOI":"10.1137\/18M1184485"},{"key":"247_CR4","doi-asserted-by":"crossref","unstructured":"G. D. Birkhoff & D. C. Lewis (1946). Chromatic polynomials. Trans. Amer. Math. Soc. 60, 355\u2013451. ISSN 0002-9947,1088-6850. URL https:\/\/doi.org\/10.2307\/1990348.","DOI":"10.1090\/S0002-9947-1946-0018401-4"},{"key":"247_CR5","unstructured":"David de Boer, Pjotr Buys, Lorenzo Guerini, Han Peters & Guus Regts (2021). Zeros, chaotic ratios and the computational complexity arXiv preprint of approximating the independence polynomial. arXiv preprint arXiv:2104.11615."},{"key":"247_CR6","doi-asserted-by":"crossref","unstructured":"Pjotr Buys (2021). Cayley trees do not determine the maximal zerofree locus of the independence polynomial. Michigan Math. J. 70(3), 635\u2013648. ISSN 0026-2285. URL https:\/\/doi-org.proxy.uba.uva.nl\/10.1307\/mmj\/1599206419.","DOI":"10.1307\/mmj\/1599206419"},{"key":"247_CR7","doi-asserted-by":"crossref","unstructured":"Pjotr Buys, Andreas Galanis, Viresh Patel & Guus Regts (2022). Lee-Yang zeros and the complexity of the ferromagnetic Ising model on bounded degree graphs. Forum Math. Sigma 10, Paper No. e7, 43. URL https:\/\/doi-org.proxy.uba.uva.nl\/10.1017\/fms.2022.4.","DOI":"10.1017\/fms.2022.4"},{"key":"247_CR8","doi-asserted-by":"crossref","unstructured":"Ivan Chio, Caleb He, Anthony L. Ji & Roland K. W. Roeder (2019). Limiting measure of Lee-Yang zeros for the Cayley tree. Comm. Math. Phys. 370(3), 925\u2013957. ISSN 0010-3616. URL https:\/\/doi-org.proxy.uba.uva.nl\/10.1007\/s00220-019-03377-9.","DOI":"10.1007\/s00220-019-03377-9"},{"key":"247_CR9","doi-asserted-by":"crossref","unstructured":"Joanna A Ellis-Monaghan & Iain Moffatt (editors) (2022). Handbook of the Tutte Polynomial and Related Topics. CRC Press.","DOI":"10.1201\/9780429161612"},{"key":"247_CR10","doi-asserted-by":"crossref","unstructured":"Roberto Fern\u00e1ndez & Aldo Procacci (2008). Regions without complex zeros for chromatic polynomials on graphs with bounded degree. Combin. Probab. Comput. 17(2), 225\u2013238. ISSN 0963-5483. URL https:\/\/doi-org.proxy.uba.uva.nl\/10.1017\/S0963548307008632.","DOI":"10.1017\/S0963548307008632"},{"key":"247_CR11","doi-asserted-by":"crossref","unstructured":"Andreas Galanis, Leslie A. Goldberg & Andres Herrera-Poyatos (2022a). The complexity of approximating the complexvalued Ising model on bounded degree graphs. SIAM J. Discrete Math. 36(3), 2159\u20132204. ISSN 0895-4801,1095-7146. URL https:\/\/doi.org\/10.1137\/21M1454043.","DOI":"10.1137\/21M1454043"},{"key":"247_CR12","doi-asserted-by":"crossref","unstructured":"Andreas Galanis, Leslie Ann Goldberg & Andr\u00e9s Herrera-Poyatos (2022b). The complexity of approximating the complexvalued Potts model. Comput. Complexity 31(1), Paper No. 2, 94. ISSN 1016-3328. URL https:\/\/doi-org.proxy.uba.uva.nl\/10.1007\/s00037-021-00218-x.","DOI":"10.1007\/s00037-021-00218-x"},{"key":"247_CR13","doi-asserted-by":"crossref","unstructured":"Andreas Galanis, Daniel \u0160tefankovi\u010d & Eric Vigoda (2015). Inapproximability for antiferromagnetic spin systems in the tree nonuniqueness region. J. ACM 62(6), Art. 50, 60. ISSN 0004-5411. URL https:\/\/doi-org.proxy.uba.uva.nl\/10.1145\/2785964.","DOI":"10.1145\/2785964"},{"key":"247_CR14","doi-asserted-by":"crossref","unstructured":"Leslie Ann Goldberg & Heng Guo (2017). The complexity of approximating complex-valued Ising and Tutte partition functions. Comput. Complexity 26(4), 765\u2013833. ISSN 1016-3328. URL https:\/\/doi-org.proxy.uba.uva.nl\/10.1007\/s00037-017-0162-2.","DOI":"10.1007\/s00037-017-0162-2"},{"key":"247_CR15","doi-asserted-by":"crossref","unstructured":"Leslie Ann Goldberg & Mark Jerrum (2008). Inapproximability of the Tutte polynomial. Inform. and Comput. 206(7), 908\u2013929. ISSN 0890-5401. URL https:\/\/doi-org.proxy.uba.uva.nl\/10.1016\/j.ic.2008.04.003.","DOI":"10.1016\/j.ic.2008.04.003"},{"key":"247_CR16","doi-asserted-by":"crossref","unstructured":"Leslie Ann Goldberg & Mark Jerrum (2012). Inapproximability of the Tutte polynomial of a planar graph. Comput. Complexity 21(4), 605\u2013642. ISSN 1016-3328. URL https:\/\/doi-org.proxy.uba.uva.nl\/10.1007\/s00037-012-0046-4.","DOI":"10.1007\/s00037-012-0046-4"},{"key":"247_CR17","doi-asserted-by":"crossref","unstructured":"Leslie Ann Goldberg & Mark Jerrum (2014). The complexity of computing the sign of the Tutte polynomial. SIAM J. Comput. 43(6), 1921\u20131952. ISSN 0097-5397. URL https:\/\/doi-org.proxy.uba.uva.nl\/10.1137\/12088330X.","DOI":"10.1137\/12088330X"},{"key":"247_CR18","doi-asserted-by":"crossref","unstructured":"Bill Jackson, Aldo Procacci & Alan D. Sokal (2013). Complex zero-free regions at large |q| for multivariate Tutte polynomials (alias Potts-model partition functions) with general complex edge weights. J. Combin. Theory Ser. B 103(1), 21\u201345. ISSN 0095-8956. URL https:\/\/doi-org.proxy.uba.uva.nl\/10.1016\/j.jctb.2012.08.002.","DOI":"10.1016\/j.jctb.2012.08.002"},{"key":"247_CR19","doi-asserted-by":"crossref","unstructured":"F. Jaeger, D. L. Vertigan & D. J. A. Welsh (1990). On the computational complexity of the Jones and Tutte polynomials. Math. Proc. Cambridge Philos. Soc. 108(1), 35\u201353. ISSN 0305-0041. URL https:\/\/doi-org.proxy.uba.uva.nl\/10.1017\/S0305004100068936.","DOI":"10.1017\/S0305004100068936"},{"key":"247_CR20","doi-asserted-by":"crossref","unstructured":"R. Kannan, A. K. Lenstra & L. Lov\u00e1sz (1988). Polynomial factorization and nonrandomness of bits of algebraic and some transcendental numbers. Math. Comp. 50(181), 235\u2013250. ISSN 0025-5718. URL https:\/\/doi-org.proxy.uba.uva.nl\/10.2307\/2007927.","DOI":"10.1090\/S0025-5718-1988-0917831-4"},{"key":"247_CR21","doi-asserted-by":"crossref","unstructured":"Michael Kowalczyk & Jin-Yi Cai (2016). Holant problems for 3-regular graphs with complex edge functions. Theory Comput. Syst. 59(1), 133\u2013158. ISSN 1432-4350. URL https:\/\/doi-org.proxy.uba.uva.nl\/10.1007\/s00224-016-9671-7.","DOI":"10.1007\/s00224-016-9671-7"},{"key":"247_CR22","doi-asserted-by":"crossref","unstructured":"A. K. Lenstra, H. W. Lenstra, Jr. & L. Lov\u00b4asz (1982). Factoring polynomials with rational coefficients. Math. Ann. 261(4), 515\u2013534. ISSN 0025-5831. URL https:\/\/doi-org.proxy.uba.uva.nl\/10.1007\/BF01457454.","DOI":"10.1007\/BF01457454"},{"key":"247_CR23","doi-asserted-by":"crossref","unstructured":"R. Loos (1983). Computing in algebraic extensions. In Computer algebra, 173\u2013187. Springer, Vienna. URL https:\/\/doi-org.proxy.uba.uva.nl\/10.1007\/978-3-7091-7551-4_12.","DOI":"10.1007\/978-3-7091-7551-4_12"},{"key":"247_CR24","doi-asserted-by":"crossref","unstructured":"K. Mahler (1964). An inequality for the discriminant of a polynomial.Michigan Math. J. 11, 257\u2013262. ISSN 0026-2285. URL http:\/\/projecteuclid.org.proxy.uba.uva.nl\/euclid.mmj\/1028999140.","DOI":"10.1307\/mmj\/1028999140"},{"key":"247_CR25","doi-asserted-by":"crossref","unstructured":"M. Mignotte (1974). An inequality about factors of polynomials. Math. Comp. 28, 1153\u20131157. ISSN 0025-5718. URL https:\/\/doi-org.proxy.uba.uva.nl\/10.2307\/2005373.","DOI":"10.1090\/S0025-5718-1974-0354624-3"},{"key":"247_CR26","doi-asserted-by":"crossref","unstructured":"Viresh Patel & Guus Regts (2017). Deterministic polynomial time approximation algorithms for partition functions and graph polynomials. SIAM J. Comput. 46(6), 1893\u20131919. ISSN 0097-5397. URL https:\/\/doi-org.proxy.uba.uva.nl\/10.1137\/16M1101003.","DOI":"10.1137\/16M1101003"},{"key":"247_CR27","doi-asserted-by":"crossref","unstructured":"Thomas J. Perrett & Carsten Thomassen (2018). Density of chromatic roots in minor-closed graph families. Combin. Probab. Comput. 27(6), 988\u2013998. ISSN 0963-5483. URL https:\/\/doi-org.proxy.uba.uva.nl\/10.1017\/S0963548318000184.","DOI":"10.1017\/S0963548318000184"},{"key":"247_CR28","doi-asserted-by":"crossref","unstructured":"Han Peters & Guus Regts (2019). On a conjecture of Sokal concerning roots of the independence polynomial. Michigan Math. J. 68(1), 33\u201355. ISSN 0026-2285. URL https:\/\/doi-org.proxy.uba.uva.nl\/10.1307\/mmj\/1541667626.","DOI":"10.1307\/mmj\/1541667626"},{"key":"247_CR29","doi-asserted-by":"crossref","unstructured":"Han Peters & Guus Regts (2020). Location of zeros for the partition function of the Ising model on bounded degree graphs. J. Lond. Math. Soc. (2) 101(2), 765\u2013785. ISSN 0024-6107. URL https:\/\/doi-org.proxy.uba.uva.nl\/10.1112\/jlms.12286.","DOI":"10.1112\/jlms.12286"},{"key":"247_CR30","unstructured":"Sven de Ronde (2023). Approximating the Chromatic polynomial is #P-hard for graphs of almost bounded degree. Master thesis, Korteweg de Vries Institute for Mathematics, University of Amsterdam."},{"key":"247_CR31","doi-asserted-by":"crossref","unstructured":"Gordon F. Royle & Alan D. Sokal (2015). Linear bound in terms of maxmaxflow for the chromatic roots of series-parallel graphs. SIAM J. Discrete Math. 29(4), 2117\u20132159. ISSN 0895-4801. URL https:\/\/doi-org.proxy.uba.uva.nl\/10.1137\/130930133.","DOI":"10.1137\/130930133"},{"key":"247_CR32","doi-asserted-by":"crossref","unstructured":"Alan D. Sokal (2001). Bounds on the complex zeros of (di)chromatic polynomials and Potts-model partition functions. Combin. Probab. Comput. 10(1), 41\u201377. ISSN 0963-5483. URL https:\/\/doi-org.proxy.uba.uva.nl\/10.1017\/S0963548300004612.","DOI":"10.1017\/S0963548300004612"},{"key":"247_CR33","doi-asserted-by":"crossref","unstructured":"Alan D. Sokal (2004). Chromatic roots are dense in the whole complex plane. Combin. Probab. Comput. 13(2), 221\u2013261. ISSN 0963-5483. URL https:\/\/doi-org.proxy.uba.uva.nl\/10.1017\/S0963548303006023.","DOI":"10.1017\/S0963548303006023"},{"key":"247_CR34","doi-asserted-by":"crossref","unstructured":"Alan D. Sokal (2005). The multivariate Tutte polynomial (alias Potts model) for graphs and matroids. In Surveys in combinatorics 2005, volume 327 of London Math. Soc. Lecture Note Ser., 173\u2013226. Cambridge Univ. Press, Cambridge. URL https:\/\/doi-org.proxy.uba.uva.nl\/10.1017\/CBO9780511734885.009.","DOI":"10.1017\/CBO9780511734885.009"},{"key":"247_CR35","doi-asserted-by":"crossref","unstructured":"Adam Wojciech Strzebo\u0144ski (1997). Computing in the field of complex algebraic numbers. J. Symbolic Comput. 24(6), 647\u2013656. ISSN 0747-7171. URL https:\/\/doi-org.proxy.uba.uva.nl\/10.1006\/jsco.1997.0158.","DOI":"10.1006\/jsco.1997.0158"},{"key":"247_CR36","doi-asserted-by":"crossref","unstructured":"Carsten Thomassen (1997). The zero-free intervals for chromatic polynomials of graphs. Combinatorics, Probability and Computing 6(4), 497\u2013506.","DOI":"10.1017\/S0963548397003131"},{"key":"247_CR37","doi-asserted-by":"crossref","unstructured":"W. T. Tutte (1970). The golden ratio in the theory of chromatic polynomials. Ann. New York Acad. Sci. 175, 391\u2013402. ISSN 0077-8923.","DOI":"10.1111\/j.1749-6632.1970.tb45159.x"},{"key":"247_CR38","doi-asserted-by":"crossref","unstructured":"Dirk Vertigan (2005). The computational complexity of Tutte invariants for planar graphs. SIAM J. Comput. 35(3), 690\u2013712. ISSN 0097-5397. URL https:\/\/doi-org.proxy.uba.uva.nl\/10.1137\/S0097539704446797.","DOI":"10.1137\/S0097539704446797"},{"key":"247_CR39","unstructured":"Michel Waldschmidt (2013). Diophantine approximation on linear algebraic groups: transcendence properties of the exponential function in several variables, volume 326. Springer Science & Business Media."},{"key":"247_CR40","doi-asserted-by":"crossref","unstructured":"Herbert S. Wilf (1978). A global bisection algorithm for computing the zeros of polynomials in the complex plane. J. Assoc. Comput. Mach. 25(3), 415\u2013420. ISSN 0004-5411. URL https:\/\/doi-org.proxy.uba.uva.nl\/10.1145\/322077.322084.","DOI":"10.1145\/322077.322084"},{"key":"247_CR41","doi-asserted-by":"crossref","unstructured":"D. R. Woodall (1997). The largest real zero of the chromatic polynomial. Discrete Math. 172(1-3), 141\u2013153. ISSN 0012-365X. URL https:\/\/doi-org.proxy.uba.uva.nl\/10.1016\/S0012-365X(96)00277-4. Chromatic polynomials and related topics (Shanghai, 1994).","DOI":"10.1016\/S0012-365X(96)00277-4"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-023-00247-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00037-023-00247-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-023-00247-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,2]],"date-time":"2024-07-02T15:39:34Z","timestamp":1719934774000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00037-023-00247-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,18]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,6]]}},"alternative-id":["247"],"URL":"https:\/\/doi.org\/10.1007\/s00037-023-00247-8","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,1,18]]},"assertion":[{"value":"13 December 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 January 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 June 2024","order":3,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Update","order":4,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"\"Copyright Year updated as 2024\"","order":5,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"1"}}