Publication Overview

Cornelius Brand and Holger Dell and Marc Roth

Fine-Grained Dichotomies for the Tutte Plane and Boolean #CSP

Jaeger, Vertigan, and Welsh [Math. Proc. Camb. Philos. Soc 90] 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. Dell, Husfeldt and Wahlén [ICALP 10] and Husfeldt and Taslaman [IPEC 10] in combination with Curticapean [ICALP 15] 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 Creignou and Hermann [Inf. Comput. 96] for counting the number of satisfying assignments to a constraint satisfaction problem instance over the Boolean domain. We prove that all #P-hard cases are also hard under #ETH. 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 [ICALP 15] and transfer it to systems of linear equations that might not directly correspond to interpolation.

Published in: 11th International Symposium on Parameterized and Exact Computation, IPEC 2016, August 24-26, Aarhus, Denmark
Year: 2016
Volume: 12
Pages: 9:1-9:14