activity
20162026
most citedCounting Induced Subgraphs: An Algebraic Approach to #W[1]-hardness

2 citations · 4 across the 7 of their papers we have counts for

collaborators
Showing 2021Show all

2 papers · 1 filter

cs.CC2021

Parameterized (Modular) Counting and Cayley Graph Expanders

Norbert Peyerimhoff, Marc Roth, Johannes Schmitt +2

We study the problem of counting -edge subgraphs satisfying a given graph property in a large host graph . Building upon the breakthrough result o…

cs.CC2021

Exact and Approximate Pattern Counting in Degenerate Graphs: New Algorithms, Hardness Results, and Complexity Dichotomies

Marco Bressan, Marc Roth

We study the problems of counting the homomorphisms, counting the copies, and counting the induced copies of a -vertex graph in a -degenerate -vertex graph . Our ma…