Fine-grained dichotomies for the Tutte plane and Boolean #CSP

Conference item

Jaeger, Vertigan, and Welsh [15] 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 [9] and Husfeldt and Taslaman [12], in combination with the results of Curticapean [7], 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 [6] 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 [7] and transfer it to systems of linear equations that might not directly correspond to interpolation.

Authors: Roth, M; Brand, C; Dell, H

• Publication status: Published
• Peer review status: Reviewed (other)
• Publisher: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
• Host title: 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)
• Journal: 11th International Symposium on Parameterized and Exact Computation
• Volume: 63
• Issue: 9
• Pages: 9:1-9:14
• Series: Leibniz International Proceedings in Informatics (LIPIcs)
• Publication date: 2017-01-01
• Acceptance date: 2016-07-24
• DOI: 10.4230/LIPIcs.IPEC.2016.9
• ISSN: 1868-8969
• ISBN: 9783959770231