2 citations · 8 across the 12 of their papers we have counts for
Showing 2019Show all
3 papers · 1 filter
cs.CC2019
Counting and Finding Homomorphisms is Universal for Parameterized Complexity Theory
Marc Roth, Philip Wellnitz
Counting homomorphisms from a graph into another graph is a fundamental problem of (parameterized) counting complexity theory. In this work, we study the case where \emph{b…
cs.CC2019★ 2 cited
Counting Induced Subgraphs: An Algebraic Approach to #W[1]-hardness
Julian Dörfler, Marc Roth, Johannes Schmitt +1
We study the problem #IndSub(P) of counting all induced subgraphs of size k in a graph G that satisfy the property P. This problem was introduced by Jerrum and Meeks and shown to b…
cs.CC2019
Counting Answers to Existential Questions
Holger Dell, Marc Roth, Philip Wellnitz
Conjunctive queries select and are expected to return certain tuples from a relational database. We study the potentially easier problem of counting all selected tuples, rather tha…