2012/06/08 by Holger Dell, Thore Husfeldt, Dániel Marx +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Binary logarithm #Chromatic polynomial #Combinatorics #Complexity and Algorithms in Graphs #Discrete mathematics #Enumeration #Exponential function #Exponential time hypothesis #Graph #Lemma (botany) #Markov Chains and Monte Carlo Methods #Mathematics #Multigraph #Satisfiability #Time complexity #Tutte polynomial #Vertex (graph theory) #cs.CC #cs.DS #math.CO
paper · pdf · doi:10.1145/2635812
published as ACM Trans. Algorithms 10(4): 21:1-21:32 (2014)
arxiv created 2012/06/08 · openalex publication_date 2014/08/01 · arxiv updated 2018/04/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
We show conditional lower bounds for well-studied #P-hard problems: The number of satisfying assignments of a 2-CNF formula with n variables cannot be computed in time exp( o ( n )), and the same is true for computing the number of all independent sets in an n -vertex graph. The permanent of an n × n matrix with entries 0 and 1 cannot be computed in time exp( o ( n )). The Tutte polynomial of an n -vertex multigraph cannot be computed in time exp( o ( n )) at most evaluation points ( x , y ) in the case of multigraphs, and it cannot be computed in time exp( o ( n /poly log n )) in the case of simple graphs. Our lower bounds are relative to (variants of) the Exponential Time Hypothesis (ETH), which says that the satisfiability of n -variable 3-CNF formulas cannot be decided in time exp( o ( n )). We relax this hypothesis by introducing its counting version #ETH; namely, that the satisfying assignments cannot be counted in time exp( o ( n )). In order to use #ETH for our lower bounds, we transfer the sparsification lemma for d -CNF formulas to the counting setting.