2 citations · 7 across the 10 of their papers we have counts for
9 papers · 1 filter
The Complexity of Finding and Counting Subtournaments
Simon Döring, Sarah Houdaigoui, Lucas Picasarri-Arrieta +1
We study the complexity of counting and finding small tournament patterns inside large tournaments. Given a fixed tournament of order , we write ${\#}\text{IndSub}_{\text{To…
The Parametrised Complexity of Counting Small Sub-Hypergraphs
Marco Bressan, Julian Brinkmann, Holger Dell +2
Subgraph counting is a fundamental and well-studied problem whose computational complexity is well understood. Quite surprisingly, the hypergraph version of subgraph counting has b…
From Graph Properties to Graph Parameters: Tight Bounds for Counting on Small Subgraphs
Simon Döring, Dániel Marx, Philip Wellnitz
A graph property is a function that maps every graph to {0, 1} and is invariant under isomorphism. In the problem, given a graph and an integer , the task…
Counting Small Induced Subgraphs with Edge-monotone Properties
Simon Döring, Dániel Marx, Philip Wellnitz
We study the parameterized complexity of #IndSub(), where given a graph and an integer , the task is to count the number of induced subgraphs on vertices that satisfy…
Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part II: Hardness Results
Jacob Focke, Dániel Marx, Fionn Mc Inerney +4
For a well-studied family of domination-type problems, in bounded-treewidth graphs, we investigate whether it is possible to find faster algorithms. For sets of non-negative…
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…