Summary: F. Jaeger et al. [Math. Proc. Camb. Philos. Soc. 108, No. 1, 35–53 (1990; Zbl 0747.57006)] proved a dichotomy for the complexity of evaluating the Tutte polynomial at fixed points: The evaluation is #P-hard almost everywhere, and the remaining points admit polynomial-time algorithms. H. Dell et al. [Lect. Notes Comput. Sci. 6198, 426–437 (2010; Zbl 1288.68111)] and T. Husfeldt and N. Taslaman [Lect. Notes Comput. Sci. 6478, 192–203 (2010; Zbl 1253.68176)], in combination with the results of R. Curticapean [Lect. Notes Comput. Sci. 9134, 380–392 (2015; Zbl 1394.68157)], extended the #P-hardness results to tight lower bounds under the counting exponential time hypothesis #ETH, with the exception of the line \(y=1\), which was left open. We complete the dichotomy theorem for the Tutte polynomial under #ETH by proving that the number of all acyclic subgraphs of a given \(n\)-vertex graph cannot be determined in time \(\exp(o(n))\) unless #ETH fails.
Another dichotomy theorem we strengthen is the one of N. Creignou and M. Hermann [Inf. Comput. 125, No. 1, 1–12 (1996; Zbl 0853.68110)] for counting the number of satisfying assignments to a constraint satisfaction problem instance over the Boolean domain. We prove that all #P-hard cases cannot be solved in time \(\exp(o(n))\) unless #ETH fails. The main ingredient is to prove that the number of independent sets in bipartite graphs with \(n\) vertices cannot be computed in time \(\exp(o(n))\) unless #ETH fails.
In order to prove our results, we use the block interpolation idea by [Curticapean, loc. cit.] and transfer it to systems of linear equations that might not directly correspond to interpolation.
For the entire collection see [Zbl 1360.68013].