max planck institut
informatik
mpii logo Minerva of the Max Planck Society

PHP Wellnitz

Max Planck Institute for Informatics
Department 1: Algorithms and Complexity
Campus E1 4, Room 324
66123, Saarbrücken
Germany

Email: wellnitzmpi-inf.mpg.de

I am a post-doctoral researcher at the Max Planck Institute for Informatics. My interests lie in algorithms and lower bounds for finding patterns in strings and graphs, mostly as seen through the lens of parametrized complexity theory. In particular, I work on (approximate) string matching. Further, I am interested in the (parametrized) counting complexity of problems such as counting how often a graph appears in another graph as an (induced) subgraph.


Selected Publications


The following lists contain only selected publications. Consult dblp for a more complete list of publications.

Finding and Counting String Patterns

(accepted) "Faster Pattern Matching under Edit Distance" [arXiv]

with Panagiotis Charalampopoulos and Tomasz Kociumaka

We give an O(n + n/m k^3.5) algorithm for PM with edits. This is the first improvement of Cole and Hariharan's [CH'02] O(n + n/m k^4) algorithm for the problem.

"Faster Approximate Pattern Matching: A Unified Approach" [arXiv] [video]

with Panagiotis Charalampopoulos and Tomasz Kociumaka

We tighten the structural insight from [BKW, SODA'19] and show a similar result for pattern matching with edits: either there are very few occurrences of a pattern in a text, or both text and pattern are close to a common highly periodic string. Using the structural insight, we obtain faster algorithms for PM with mismatches and edits for the fully-compressed and other settings.

Finding and Counting (Small) Graph Patterns

"Counting Small Induced Subgraphs Satisfying Monotone Properties" [arXiv] [journal]

with Marc Roth and Johannes Schmitt

We show that for any (non-trivial) monotone graph property Φ, counting all induced subgraphs of a graph that satisy Φ is #W[1]-hard and no significant improvement upon the brute-force algorithms is possible (unless ETH fails).

"Counting and Finding Homomorphisms is Universal for Parameterized Complexity Theory" [arXiv] [slides]

with Marc Roth

We show that any problem P in #W[1] (or W[1]) is equivalent to the problem of counting homomorphisms between graphs of graph classes H(P) and G(P).


Code



Recent Teaching



Short CV