11 citations · 19 across the 15 of their papers we have counts for
22 papers
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…
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…
Near-Optimal-Time Quantum Algorithms for Approximate Pattern Matching
Tomasz Kociumaka, Jakob Nogler, Philip Wellnitz
Approximate Pattern Matching is among the most fundamental string-processing tasks. Given a text of length , a pattern of length , and a threshold , the task is to…
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…
On the Communication Complexity of Approximate Pattern Matching
Tomasz Kociumaka, Jakob Nogler, Philip Wellnitz
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), as…
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 such…
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…
Optimal Algorithms for Bounded Weighted Edit Distance
Alejandro Cassis, Tomasz Kociumaka, Philip Wellnitz
The edit distance of two strings is the minimum number of insertions, deletions, and substitutions of characters needed to transform one string into the other. The textbook dynamic…
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 -set o…
Faster Pattern Matching under Edit Distance
Panagiotis Charalampopoulos, Tomasz Kociumaka, Philip Wellnitz
We consider the approximate pattern matching problem under the edit distance. Given a text of length , a pattern of length , and a threshold , the task is to find…
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…
On Near-Linear-Time Algorithms for Dense Subset Sum
Karl Bringmann, Philip Wellnitz
In the Subset Sum problem we are given a set of positive integers and a target and are asked whether some subset of sums to . Natural parameters for this problem…
Faster Minimization of Tardy Processing Time on a Single Machine
Karl Bringmann, Nick Fischer, Danny Hermelin +2
This paper is concerned with the problem, the problem of minimizing the total processing time of tardy jobs on a single machine. This is not only a fundamental sch…
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 …
Faster Approximate Pattern Matching: A Unified Approach
Panagiotis Charalampopoulos, Tomasz Kociumaka, Philip Wellnitz
Approximate pattern matching is a natural and well-studied problem on strings: Given a text , a pattern , and a threshold , find (the starting positions of) all substrings…
Counting and Finding Homomorphisms is Universal for Parameterized Complexity Theory
Marc Roth, Philip Wellnitz
Counting homomorphisms from a graph into another graph is a fundamental problem of (parameterized) counting complexity theory. In this work, we study the case where \emph{b…
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…
Clique-Based Lower Bounds for Parsing Tree-Adjoining Grammars
Karl Bringmann, Philip Wellnitz
Tree-adjoining grammars are a generalization of context-free grammars that are well suited to model human languages and are thus popular in computational linguistics. In the tree-a…