121 citations · 416 across the 16 of their papers we have counts for
5 papers · 1 filter
Note on "The Complexity of Counting Surjective Homomorphisms and Compactions"
Holger Dell
Focke, Goldberg, and Živný (arXiv 2017) prove a complexity dichotomy for the problem of counting surjective homomorphisms from a large input graph G without loops to a fixed graph…
Fine-grained reductions from approximate counting to decision
Holger Dell, John Lapinskas
In this paper, we introduce a general framework for fine-grained reductions of approximate counting problems to their decision versions. (Thus we use an oracle that decides whether…
Homomorphisms Are a Good Basis for Counting Small Subgraphs
Radu Curticapean, Holger Dell, Dániel Marx
We introduce graph motif parameters, a class of graph parameters that depend only on the frequencies of constant-size induced subgraphs. Classical works by Lovász show that many in…
A Fixed-Parameter Perspective on #BIS
Radu Curticapean, Holger Dell, Fedor Fomin +2
The problem of (approximately) counting the independent sets of a bipartite graph (#BIS) is the canonical approximate counting problem that is complete in the intermediate complexi…
Counting edge-injective homomorphisms and matchings on restricted graph classes
Radu Curticapean, Holger Dell, Marc Roth
We consider the -hard problem of counting all matchings with exactly edges in a given input graph ; we prove that it remains -hard on graph…