2 citations · 2 across the 2 of their papers we have counts for
3 papers
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.CC2017
Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices
Marc Roth
We present a framework for the complexity classification of parameterized counting problems that can be formulated as the summation over the numbers of homomorphisms from small pat…
cs.CC2016
Fine-grained dichotomies for the Tutte plane and Boolean #CSP
Cornelius Brand, Holger Dell, Marc Roth
Jaeger, Vertigan, and Welsh [15] proved a dichotomy for the complexity of evaluating the Tutte polynomial at fixed points: The evaluation is #P-hard almost everywhere, and the rema…