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.

Previous chapter Next chapter Full AccessProceedings Proceedings of the 2012 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)Shortest Cycle Through Specified ElementsAndreas Björklund, Thore Husfeldt, and Nina TaslamanAndreas BjörklundLund University, Sweden.Lund University, Sweden, and IT University of Copenhagen, Denmark.IT University of Copenhagen, Denmark., Thore HusfeldtLund University, Sweden.Lund University, Sweden, and IT University of Copenhagen, Denmark.IT University of Copenhagen, Denmark., and Nina TaslamanLund University, Sweden.Lund University, Sweden, and IT University of Copenhagen, Denmark.IT University of Copenhagen, Denmark.pp.1747 - 1753Chapter DOI:https://doi.org/10.1137/1.9781611973099.139PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstract We give a randomized algorithm that finds a shortest simple cycle through a given set of k vertices or edges in an n-vertex undirected graph in time 2knO(1). Previous chapter Next chapter RelatedDetails Published:2012ISBN:978-1-61197-210-8eISBN:978-1-61197-309-9 https://doi.org/10.1137/1.9781611973099Book Series Name:ProceedingsBook Code:PR141Book Pages:xiii + 1757