Goldberg and Jerrum (Journal of the ACM, 2012) proved that approximating the partition function of the ferromagnetic q-state Potts model on general graphs — equivalently the Tutte-polynomial evaluation problem Tutte(q,γ) with q>2 and edge parameter γ>0 — is hard for the counting class #BIS under approximation-preserving (AP) reductions: #BIS ≤_AP Tutte(q,γ). The paper explicitly leaves open the converse: whether Tutte(q,γ) ≤_AP #BIS, which would make the two problems AP-interreducible and place the ferromagnetic Potts partition function exactly in the #BIS equivalence class.

Background

The q-state Potts model is a spin system on a graph G=(V,E): each vertex carries a spin σ(v)∈{1,…,q}, and the partition function is ZPotts(G;q,γ)=∑σ:V→[q]∏e={u,v}(1+γ δ(σ(u),σ(v)))Z_{\mathrm{Potts}}(G;q,\gamma)=\sum_{\sigma:V\to[q]}\prod_{e=\{u,v\}}(1+\gamma\,\delta(\sigma(u),\sigma(v))), where δ is the Kronecker delta. For edge interaction γ>0 equal spins on an edge are favored (the ferromagnetic regime). Via the random-cluster representation (a probability distribution on spanning subgraphs F⊆E with weight qκ(V,F)γ∣F∣q^{\kappa(V,F)}\gamma^{|F|}, where κ(V,F) is the number of connected components), this equals the Tutte-polynomial evaluation ZTutte(G;q,γ)Z_{\mathrm{Tutte}}(G;q,\gamma), so the computational problem Tutte(q,γ) — input just the graph G, with q>2 and γ>0 fixed rational (or efficiently approximable real) constants — is exactly the problem of approximating the ferromagnetic Potts partition function. An FPRAS (fully polynomial randomized approximation scheme) is a randomized algorithm achieving relative error ε in time polynomial in the input size and 1/ε. An AP-reduction (approximation-preserving reduction) A≤APBA \le_{\mathrm{AP}} B is a polynomial-time Turing reduction whose accuracy parameter degrades only polynomially, so that an FPRAS for B yields an FPRAS for A; the induced partial order on approximate counting problems is finer than the classification of #P problems by exact-computation hardness (for example, exactly counting independent sets in bipartite graphs is #P-complete, yet #BIS is believed far easier to approximate than #SAT). #BIS, the problem of counting independent sets in a bipartite graph, is the canonical problem of intermediate complexity: it is not known to have an FPRAS, yet no NP-hardness of approximation is known for it either, and it is complete for the class #RHΠ₁ of restricted logically-defined counting problems. Many natural problems are known to be at least as hard as #BIS but resist both FPRASs and inapproximability proofs: counting downsets, i.e. order ideals of a partially ordered set, is #BIS-equivalent, while for the ferromagnetic Potts model only the #BIS-hardness direction is known (Goldberg and Jerrum, Theorem 1). Goldberg and Jerrum proved Theorem 1: for every efficiently approximable pair q>2 and γ>0, #BIS ≤_AP Tutte(q,γ), obtained by a randomized gadget construction that exploits the first-order phase transition of the random-cluster model (a discontinuity in the structure of the dominant phase as γ varies, which the gadget converts into a sharp conditional weight). Their hardness is thus conditional on the conjectured absence of an FPRAS for #BIS, which the authors state explicitly, rather than on a standard NP-vs-RP assumption. By contrast, ferromagnetic two-spin systems (Ising, q=2) without external field do admit randomized FPRASs on all graphs (Jerrum–Sinclair for the Ising model, Goldberg–Jerrum–Paterson for general ferromagnetic two-spin systems), so the q>2 ferromagnetic quadrant is the principal genuinely unresolved region of the approximation complexity map of the Potts/Tutte plane.

Problem Statement

For fixed constants q>2 and γ>0 (rational, or more generally efficiently approximable real parameters), determine whether the problem Tutte(q,γ) of approximating the ferromagnetic Potts/Tutte partition function ZTutte(G;q,γ)=∑F⊆Eqκ(V,F)γ∣F∣Z_{\mathrm{Tutte}}(G;q,\gamma)=\sum_{F\subseteq E}q^{\kappa(V,F)}\gamma^{|F|} on an input graph G is AP-reducible to #BIS — that is, whether Tutte(q,γ)≤AP#BIS\mathrm{Tutte}(q,\gamma)\le_{\mathrm{AP}}\#\mathrm{BIS}, completing the AP-interreducibility with #BIS established in the forward direction by Goldberg and Jerrum's Theorem 1. The scope matches that of Theorem 1, which is region-wide: each efficiently approximable pair q>2, γ>0 defines a separate computational problem whose input is just the graph G, and a resolution should answer the reduction question across the ferromagnetic region rather than for a single isolated pair. An FPRAS for Tutte(q,γ) on all input graphs would settle the reduction question affirmatively for the region, and composed with Theorem 1 would also yield an FPRAS for #BIS, contradicting the authors' conjecture that #BIS admits no FPRAS. The question is entangled with, but distinct from, that conjecture: the conjecture motivates the conditional form of the known #BIS-hardness — the authors state that their inapproximability is conditional on there being no FPRAS for #BIS rather than on the weaker assumption NP≠RP — but it leaves the converse reduction question fully intact.

References

  1. Leslie Ann Goldberg and Mark Jerrum, 'Approximating the partition function of the ferromagnetic Potts model', Journal of the ACM 59(5), Article 25, pp. 1–31, 2012. DOI: 10.1145/2371656.2371660, https://doi.org/10.1145/2371656.2371660; arXiv:1002.0986, https://arxiv.org/abs/1002.0986
  2. Andreas Galanis, Daniel Štefankovič, Eric Vigoda, and Linji Yang, 'Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results', SIAM Journal on Computing 45(6), pp. 2004–2065, 2016. DOI: 10.1137/140997580, https://doi.org/10.1137/140997580; arXiv:1311.4839, https://arxiv.org/abs/1311.4839
  3. Andreas Galanis, Leslie Ann Goldberg, and Andrés Herrera-Poyatos, 'The complexity of approximating the complex-valued Potts model', Computational Complexity 31(1), Article 2, 2022. DOI: 10.1007/s00037-021-00218-x, https://doi.org/10.1007/s00037-021-00218-x; arXiv:2005.01076, https://arxiv.org/abs/2005.01076
  4. Charlie Carlson, Ewan Davies, Nicolas Fraiman, Alexandra Kolla, Aditya Potukuchi, and Corrine Yap, 'Algorithms for the ferromagnetic Potts model on expanders', Combinatorics, Probability and Computing 33(4), pp. 487–517, 2024. DOI: 10.1017/S0963548324000087, https://doi.org/10.1017/S0963548324000087; arXiv:2204.01923, https://arxiv.org/abs/2204.01923
  5. Zonglei Bai, Yongzhi Cao, and Hanpin Wang, 'FPRAS for the Potts Model and the Number of k-colorings', arXiv:1902.09114 (2019), withdrawn by the authors in v3 (27 February 2019) with the comment 'We find an error in the analysis of the algorithm, and it makes the results wrong', https://arxiv.org/abs/1902.09114
  6. Andreas Galanis, Daniel Štefankovič, and Eric Vigoda, 'Inapproximability for Antiferromagnetic Spin Systems in the Tree Nonuniqueness Region', Journal of the ACM 62(6), pp. 1–60, 2015. DOI: 10.1145/2785964, https://doi.org/10.1145/2785964
  7. Andreas Galanis, Daniel Štefankovič, and Eric Vigoda, 'Approximating observables is as hard as counting', Proceedings of ICALP 2022, Leibniz International Proceedings in Informatics (LIPIcs), vol. 229, pp. 63:1–63:18. DOI: 10.4230/LIPIcs.ICALP.2022.63, https://doi.org/10.4230/LIPIcs.ICALP.2022.63; arXiv:2206.11606, https://arxiv.org/abs/2206.11606
  8. Jingcheng Liu and Pinyan Lu, 'FPTAS for Counting Monotone CNF', Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), pp. 1531–1548. DOI: 10.1137/1.9781611973730.101, https://doi.org/10.1137/1.9781611973730.101
  9. Matthew Jenssen, Will Perkins, and Aditya Potukuchi, 'Approximately counting independent sets in bipartite graphs via graph containers', Random Structures & Algorithms 63(1), pp. 215–241, 2023. DOI: 10.1002/rsa.21145, https://doi.org/10.1002/rsa.21145
  10. Heng Guo and Mark Jerrum, 'A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability', SIAM Journal on Computing 48(3), pp. 964–978, 2019. DOI: 10.1137/18M1201846, https://doi.org/10.1137/18M1201846
  11. Charlie Carlson, Ewan Davies, Alexandra Kolla, and Aditya Potukuchi, 'Approximately counting independent sets in dense bipartite graphs via subspace enumeration', arXiv preprint, 2023. arXiv:2307.09533, https://arxiv.org/abs/2307.09533
  12. Maurício Collares, Joshua Erde, Anna Geisler, and Mihyun Kang, 'Counting independent sets in expanding bipartite regular graphs', arXiv preprint, 2025. arXiv:2503.22255, https://arxiv.org/abs/2503.22255
  13. Ijay Narang, Will Perkins, Yuzhou Wang, and Timothy L. H. Wee, 'Computational Thresholds for Balanced and Fixed-Slice Independent Sets in Bipartite Graphs', arXiv preprint, 2026. arXiv:2608.02503, https://arxiv.org/abs/2608.02503
  14. Weiming Feng, Yucheng Fu, and Heng Guo, 'Approximating two-terminal network reliability', arXiv preprint, 2026. arXiv:2608.02523, https://arxiv.org/abs/2608.02523
  15. Zongchen Chen, Andreas Galanis, Leslie Ann Goldberg, Xandru Mifsud, Paulina Smolarova, and Xusheng Zhang, 'Fast Mixing for Low-Temperature Potts Models via Poisson Trees', arXiv preprint, 2026. arXiv:2607.29495, https://arxiv.org/abs/2607.29495