2 citations · 4 across the 7 of their papers we have counts for
Showing 2019Show all
2 papers · 1 filter
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…