2 citations · 3 across the 3 of their papers we have counts for
9 papers · 1 filter
The Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree
Marco Bressan, Matthias Lanzinger, Marc Roth
We study the fixed-parameter tractability of the following fundamental problem: given two directed graphs and , count the number of copies of in .…
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…
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…
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 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 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…