Completing the approximability classification of the parameterized Tutte polynomial at rational points with $(x-1)(y-1)\notin[0,1]$

Roth, Schmitt and Wellnitz (ICALP 2021) introduced the parameterized Tutte polynomial $T^k_G(x,y)$, the restriction of the classical Tutte polynomial's defining sum to edge subsets of cardinality exactly $k$, and completely classified its exact evaluation complexity over rational coordinates: polynomial time on the hyperbola $(x-1)(y-1)=1$ and at $(1,1)$, fixed-parameter tractable but #P-hard on the line $x=1$, and #W[1]-hard at every other rational point. For randomized approximation they proved that an FPTRAS exists at all rational points with $0\le(x-1)(y-1)\le1$ (an FPRAS if additionally $x\neq1$ or $y=1$), via log-concavity of the graphic matroid's basis-generating polynomial, and explicitly left the approximability of every rational point outside this region open. The problem is to complete the approximability classification of the rational parameterized Tutte plane: for each rational point with $(x-1)(y-1)<0$ or $(x-1)(y-1)>1$, either construct an FPTRAS or FPRAS, or prove that none exists under a standard hypothesis of parameterized counting complexity.

Background

The Tutte polynomial is a two-variable graph invariant

$$T_G(x,y)=\sum_{A\subseteq E(G)}(x-1)^{k(A)-k(E(G))}\cdot(y-1)^{k(A)+|A|-|V(G)|},$$

where $k(S)$ denotes the number of connected components of the spanning subgraph $(V(G),S)$. It simultaneously encodes many classical invariants — the chromatic polynomial, the flow polynomial, the number of spanning trees — and coincides, up to a change of variables, with the partition function of the $q$-state Potts model of statistical mechanics for $q=(x-1)(y-1)$, the central object in the study of exactly solved lattice models. Jaeger, Vertigan and Welsh (1990) completely classified the computational complexity of exactly evaluating $T_G$ at every fixed pair of complex coordinates; over rational coordinates, the evaluation is polynomial-time computable only on the hyperbola $(x-1)(y-1)=1$ and at the four exceptional points $(1,1)$, $(-1,-1)$, $(0,-1)$, $(-1,0)$, and #P-hard at every other rational point, where #P is the counting analogue of NP.

This record concerns a parameterized analogue introduced by Roth, Schmitt and Wellnitz (ICALP 2021). In parameterized complexity, a problem is fixed-parameter tractable (FPT) with respect to a parameter $k$ if it is solvable in time $f(k)\cdot|G|^{O(1)}$ for a computable function $f$; the counting analogue of NP-hardness is #W[1]-hardness, and conditional running-time lower bounds are usually stated under the Exponential Time Hypothesis (ETH), which asserts that 3-SAT requires $2^{\Omega(n)}$ time. Writing $\binom{E(G)}{k}$ for the family of edge subsets of size exactly $k$, the parameterized Tutte polynomial is

$$T^k_G(x,y)=\sum_{A\in\binom{E(G)}{k}}(x-1)^{k(A)-k(E(G))}\cdot(y-1)^{k(A)+k-|V(G)|},$$

with input $(G,k)$ and parameter $k$; it is the classical sum restricted to $k$-edge subsets, i.e., a weighted count of small subgraph patterns. Many classical interpretations survive the restriction: $T^k_G(2,1)$ equals the number of $k$-edge forests of $G$; $T^k_G(1-c,0)$ for integer $c$ determines the number of pairs $(A,\sigma)$ where $A$ is a $k$-edge subset and $\sigma$ is a proper $c$-coloring of $(V(G),A)$; $T^k_G(2,0)$ determines the number of pairs $(A,\eta)$ with $\eta$ an acyclic orientation of $(V(G),A)$, and the number of $k$-edge subsets whose induced graph has even Betti number (the rank of its cycle space); $T^k_G(0,2)$ determines the number of $k$-edge subsets spanning an even number of connected components.

Roth, Schmitt and Wellnitz completely classified exact computation over the rational points of the Tutte plane: computing $T^k_G(x,y)$ is polynomial-time computable if $(x,y)=(1,1)$ or $(x-1)(y-1)=1$, fixed-parameter tractable but #P-hard on the line $x=1$ ($y\neq1$), and #W[1]-hard at every other rational point. The hardness proofs express $T^k_G(x,y)$ as a linear combination of graph homomorphism counts (counts of edge-preserving vertex maps between graphs) and apply the complexity-monotonicity framework of Curticapean, Dell and Marx (STOC 2017), with coefficients controlled through the symmetry groups of toroidal grids (grid graphs with wrapped-around boundaries, i.e., Cartesian products of cycles) and Cayley graph expanders of 2-groups (sparse, highly connected graphs constructed from group multiplication tables).

For randomized approximation, the relevant notion is a fixed-parameter tractable randomized approximation scheme (FPTRAS), going back to Arvind and Raman (2002): a randomized algorithm that, on input $(G,k,\varepsilon,\delta)$, outputs in time $f(k)\cdot\mathrm{poly}(|G|,\varepsilon^{-1},\log(1/\delta))$ a value within a factor $(1\pm\varepsilon)$ of the true answer with probability at least $1-\delta$; if $f$ is a polynomial, the scheme is an FPRAS, the parameterized analogue of the classical fully polynomial randomized approximation scheme. Since $T^k_G(x,y)$ can be negative, the source paper uses the convention that the algorithm outputs a pair $(z,s)$ approximating the absolute value and returning the correct sign. The main positive result of the source paper states that $T^k_G(x,y)$ admits an FPTRAS whenever $0\le(x-1)(y-1)\le1$, and even an FPRAS if additionally $x\neq1$ or $y=1$; the proof reduces to the multivariate basis-generating polynomial of the graphic matroid (the matroid whose independent sets are the forests of $G$, so that its bases are the spanning trees), which is log-concave precisely in this region — its logarithm is a concave function on the positive orthant, the property that enables sampling — and applies the FPRAS of Anari, Liu, Oveis Gharan and Vinzant (STOC 2019) for counting matroid bases via high-dimensional random walks. The source paper emphasizes that while the classification of exact computation is complete, 'the complexity of approximation remains open outside of the coloured area' — that is, at every rational point with $(x-1)(y-1)<0$ or $(x-1)(y-1)>1$.

This gap is not an artifact of an overlooked classical result. Classical FPRASs for the unrestricted Tutte polynomial are known only for special graph classes — e.g., dense graphs (Alon, Frieze and Welsh 1995; extended to subdense graphs by Hauptmann and Tiling 2022) — and such results say nothing about the cardinality-restricted sum defining $T^k_G$, in which exponentially many weighted terms of vastly different magnitudes (and, for $(x-1)(y-1)<0$, mixed signs) must be combined; conversely, the #W[1]-hardness of exact computation does not by itself rule out multiplicative approximation, since no general transfer from exact hardness to parameterized approximation hardness is known.

Problem Statement

For every pair of rational numbers $(x,y)$ with $(x-1)(y-1)\notin[0,1]$ — equivalently, with $(x-1)(y-1)<0$ or $(x-1)(y-1)>1$ — determine the parameterized approximation complexity of computing

$$T^k_G(x,y)=\sum_{A\in\binom{E(G)}{k}}(x-1)^{k(A)-k(E(G))}\cdot(y-1)^{k(A)+k-|V(G)|}$$

on input $(G,k)$ with parameter $k$, where $k(S)$ denotes the number of connected components of the spanning subgraph $(V(G),S)$ and $\binom{E(G)}{k}$ denotes the family of $k$-element subsets of the edge set of $G$. Approximation is understood in the sign-plus-magnitude sense of Roth, Schmitt and Wellnitz, since $T^k_G(x,y)$ can be negative: the algorithm outputs a pair $(z,s)$ with $z$ within a factor $(1\pm\varepsilon)$ of $|T^k_G(x,y)|$ and $s$ the correct sign, with probability at least $1-\delta$, in time $f(k)\cdot\mathrm{poly}(|G|,\varepsilon^{-1},\log(1/\delta))$; such a scheme is an FPTRAS, and an FPRAS if $f$ is a polynomial. For each such point, either construct an FPTRAS (and, where possible, an FPRAS), or prove that no such scheme exists under a standard hypothesis of parameterized counting complexity (for example, $\mathsf{W[1]}\neq\mathsf{FPT}$ under randomized parameterized reductions, or the randomized Exponential Time Hypothesis). The completion boundary is a dichotomy for the rational parameterized Tutte plane matching the completeness of the known exact classification: an explicit partition of $\{(x,y)\in\mathbb{Q}^2:(x-1)(y-1)\notin[0,1]\}$ into points that admit an FPTRAS or FPRAS (with the algorithms and their correctness proofs) and points at which approximation is provably hard. The classification may be presented point-wise or region-wise, but completing any single point or listed subregion is a partial result that does not by itself satisfy the completion boundary; the following subregions are natural targets within the required partition: the all-positive-weight sector $\{x>1, y>1, (x-1)(y-1)>1\}$ (e.g., the point $(2,3)$), the mixed-sign sector with $(x-1)(y-1)<0$ (e.g., $(0,2)$ and $(2,0)$, which determine parity-type counts of $k$-edge subsets), and the points $(1-c,0)$ for integers $c\ge2$ (coloring-type counts of $k$-edge subsets).

References

1. Marc Roth, Johannes Schmitt, Philip Wellnitz (2021). Detecting and Counting Small Subgraphs, and Evaluating a Parameterized Tutte Polynomial: Lower Bounds via Toroidal Grids and Cayley Graph Expanders. ICALP 2021, LIPIcs vol. 198, art. 108. DOI 10.4230/LIPIcs.ICALP.2021.108, https://doi.org/10.4230/LIPIcs.ICALP.2021.108 (preprint arXiv:2011.03433, https://arxiv.org/abs/2011.03433).
2. F. Jaeger, D. L. Vertigan, D. J. A. Welsh (1990). On the computational complexity of the Jones and Tutte polynomials. Mathematical Proceedings of the Cambridge Philosophical Society 108(1), 35-53. DOI 10.1017/S0305004100068936, https://doi.org/10.1017/S0305004100068936
3. Nima Anari, Kuikui Liu, Shayan Oveis Gharan, Cynthia Vinzant (2019). Log-concave polynomials II: high-dimensional walks and an FPRAS for counting bases of a matroid. STOC 2019, pp. 1-12. DOI 10.1145/3313276.3316385, https://doi.org/10.1145/3313276.3316385
4. V. Arvind, Venkatesh Raman (2002). Approximation Algorithms for Some Parameterized Counting Problems. ISAAC 2002, LNCS 2518, pp. 453-464. DOI 10.1007/3-540-36136-7_40, https://doi.org/10.1007/3-540-36136-7_40
5. Radu Curticapean, Holger Dell, Dániel Marx (2017). Homomorphisms are a good basis for counting small subgraphs. STOC 2017, pp. 210-223. DOI 10.1145/3055399.3055502, https://doi.org/10.1145/3055399.3055502
6. Marc Roth, Johannes Schmitt, Philip Wellnitz (2020). Counting Small Induced Subgraphs Satisfying Monotone Properties. FOCS 2020, pp. 1356-1367. DOI 10.1109/FOCS46700.2020.00128, https://doi.org/10.1109/FOCS46700.2020.00128
7. Norbert Peyerimhoff, Marc Roth, Johannes Schmitt, Jakob Stix, Alina Vdovina, Philip Wellnitz (2023). Parameterized Counting and Cayley Graph Expanders. SIAM Journal on Discrete Mathematics 37(2), 405-486. DOI 10.1137/22M1479804, https://doi.org/10.1137/22M1479804 (conference version: Parameterized (Modular) Counting and Cayley Graph Expanders, MFCS 2021, LIPIcs art. 84, DOI 10.4230/LIPICS.MFCS.2021.84)
8. Marc Roth (2026). Parameterised counting complexity theory. Computer Science Review 59, 100837. DOI 10.1016/j.cosrev.2025.100837, https://doi.org/10.1016/j.cosrev.2025.100837
9. Isja Mannens, Jesper Nederlof (2023). A Fine-Grained Classification of the Complexity of Evaluating the Tutte Polynomial on Integer Points Parameterized by Treewidth and Cutwidth. ESA 2023, LIPIcs vol. 274, art. 82. DOI 10.4230/LIPIcs.ESA.2023.82, https://doi.org/10.4230/LIPIcs.ESA.2023.82
10. Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Živný (2022). Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations. PODS 2022, pp. 315-324. DOI 10.1145/3517804.3526231, https://doi.org/10.1145/3517804.3526231
11. Talya Eden, Reut Levi, Dana Ron, Ronitt Rubinfeld (2025). Approximately Counting and Sampling Hamiltonian Motifs in Sublinear Time. STOC 2025, pp. 1043-1054. DOI 10.1145/3717823.3718160, https://doi.org/10.1145/3717823.3718160
12. Radu Curticapean, Daniel Neuen (2025). Counting Small Induced Subgraphs: Hardness via Fourier Analysis. SODA 2025, pp. 3677-3695. DOI 10.1137/1.9781611978322.122, https://doi.org/10.1137/1.9781611978322.122
13. Radu Curticapean, Simon Döring, Daniel Neuen (2025). Counting Small Induced Subgraphs: Scorpions Are Easy but Not Trivial. ESA 2025, LIPIcs art. 96. DOI 10.4230/LIPICS.ESA.2025.96, https://doi.org/10.4230/LIPICS.ESA.2025.96
14. Marco Bressan, Julian Christoph Brinkmann, Holger Dell, Marc Roth, Philip Wellnitz (2026). The Parameterised Complexity of Counting Small Sub-Hypergraphs. SODA 2026, pp. 2002-2014. DOI 10.1137/1.9781611978971.72, https://doi.org/10.1137/1.9781611978971.72 (preprint arXiv:2506.14081, https://arxiv.org/abs/2506.14081, titled 'The Parametrised Complexity of Counting Small Sub-Hypergraphs')
15. Leslie Ann Goldberg, Marc Roth (2023). Parameterised and Fine-Grained Subgraph Counting, Modulo 2. Algorithmica 86(4), 944-1005. DOI 10.1007/s00453-023-01178-0, https://doi.org/10.1007/s00453-023-01178-0
16. Holger Dell, John Lapinskas, Kitty Meeks (2022). Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle. SIAM Journal on Computing 51(4), 849-899. DOI 10.1137/19M130604X, https://doi.org/10.1137/19M130604X
17. Mathias Hauptmann, Ronja Tiling (2022). Randomized Approximation Schemes for the Tutte Polynomial and Random Clustering in Subdense and Superdense Graphs. arXiv:2208.13809, https://arxiv.org/abs/2208.13809
18. Norbert Peyerimhoff, Alina Vdovina (2011). Cayley graph expanders and groups of finite width. Journal of Pure and Applied Algebra 215(11), 2780-2788. DOI 10.1016/j.jpaa.2011.03.018, https://doi.org/10.1016/j.jpaa.2011.03.018
19. Noga Alon, Alan Frieze, Dominic Welsh (1995). Polynomial time randomized approximation schemes for Tutte-Gröthendieck invariants: The dense case. Random Structures & Algorithms 6(4), 459-478. DOI 10.1002/rsa.3240060409, https://doi.org/10.1002/rsa.3240060409