We devise a framework for proving tight lower bounds under the counting exponential-time hypothesis #ETH introduced by Dell et al. Our framework allows to convert many known #P-hardness results for counting problems into results of the following type: If the given problem admits an algorithm with running time 2~(o(n)) on graphs with n vertices and O(n) edges, then #ETH fails. As exemplary applications of this framework, we obtain such tight lower bounds for the evaluation of the zero-one permanent, the matching polynomial, and the Tutte polynomial on all non-easy points except for two lines.
展开▼
