1 citations · 1 across the 1 of their papers we have counts for
8 papers
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…
The Communication Complexity of Pattern Matching with Edits Revisited
Tomasz Kociumaka, Jakob Nogler, Philip Wellnitz
In the decades-old Pattern Matching with Edits problem, given a length- string (the text), a length- string (the pattern), and a positive integer (the threshold),…
Pattern Matching under Weighted Edit Distance
Panagiotis Charalampopoulos, Tomasz Kociumaka, Philip Wellnitz
In Pattern Matching with Weighted Edits (PMWED), we are given a pattern of length , a text of length , a positive threshold , and oracle access to a weight functio…
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…
Residue Domination in Bounded-Treewidth Graphs
Jakob Greilhuber, Philipp Schepper, Philip Wellnitz
For the vertex selection problem -DomSet one is given two fixed sets and of integers and the task is to decide whether we can select vertices of the input graph…
Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part I: Algorithmic Results
Jacob Focke, Dániel Marx, Fionn Mc Inerney +4
We investigate how efficiently a well-studied family of domination-type problems can be solved on bounded-treewidth graphs. For sets of non-negative integers, a -s…