50 citations · 108 across the 18 of their papers we have counts for
5 papers · 1 filter
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…
Detecting and Counting Small Subgraphs, and Evaluating a Parameterized Tutte Polynomial: Lower Bounds via Toroidal Grids and Cayley Graph Expanders
Marc Roth, Johannes Schmitt, Philip Wellnitz
Given a graph property , we consider the problem , where the input is a pair of a graph and a positive integer , and the task is to decide whether $G…
Counting Small Induced Subgraphs Satisfying Monotone Properties
Marc Roth, Johannes Schmitt, Philip Wellnitz
Given a graph property , the problem asks, on input a graph and a positive integer , to compute the number of induced subgraphs of size in …
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…
Counting Induced Subgraphs: A Topological Approach to #W[1]-hardness
Marc Roth, Johannes Schmitt
We investigate the problem of counting all induced subgraphs of size in a graph that satisfy a given property . This continues the work of Jerrum…