89 citations · 138 across the 17 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2021
Modular counting of subgraphs: Matchings, matching-splittable graphs, and paths
Radu Curticapean, Holger Dell, Thore Husfeldt
We systematically investigate the complexity of counting subgraph patterns modulo fixed integers. For example, it is known that the parity of the number of -matchings can be det…
cs.CC2012★ 89 cited
Exponential Time Complexity of the Permanent and the Tutte Polynomial
Holger Dell, Thore Husfeldt, Dániel Marx +2
We show conditional lower bounds for well-studied #P-hard problems: (a) The number of satisfying assignments of a 2-CNF formula with n variables cannot be counted in time exp(o(n))…
cs.CC2010★ 9 cited
The Exponential Time Complexity of Computing the Probability That a Graph is Connected
Thore Husfeldt, Nina Taslaman
We show that for every probability p with 0 < p < 1, computation of all-terminal graph reliability with edge failure probability p requires time exponential in Omega(m/ log^2 m) fo…