Philip Wellnitz

SODA Conference 2025 Conference Paper

From Graph Properties to Graph Parameters: Tight Bounds for Counting on Small Subgraphs

• Simon Döring
• Dániel Marx
• Philip Wellnitz

SODA Conference 2025 Conference Paper

Near-Optimal-Time Quantum Algorithms for Approximate Pattern Matching

• Tomasz Kociumaka
• Jakob Nogler
• Philip Wellnitz

FOCS Conference 2025 Conference Paper

Pattern Matching under Weighted Edit Distance

• Panagiotis Charalampopoulos
• Tomasz Kociumaka
• Philip Wellnitz

In Pattern Matching with Weighted Edits (PMwWE), we are given a pattern P of length m, a text T of length n, a positive threshold k, and oracle access to a weight function that specifies the costs of edits (depending on the involved characters, and normalized so that the cost of each edit is at least 1). The goal is to compute the starting positions of all fragments of T that can be obtained from P with edits of total cost at most k. PMwWE captures typical real-world applications more accurately than its unweighted variant (PMwE), where all edits have unit costs. Indeed, the textbook $\mathcal{O}\left( {nm} \right)$-time algorithm of Sellers [J. Algorithms'80], devised in the context of bioinformatics, already accounts for weights. Surprisingly, the understanding of PMWWE has not advanced in the last 45 years. In contrast, significant milestones for PMwE include an $\mathcal{O}\left( {nk} \right)$-time algorithm by Landau and Vishkin [STOC'86, J. Algorithms'89], an $\mathcal{O}(n + {k^4} \cdot n/m)$-time algorithm by Cole and Hariharan [SODA'98, SICOMP'02], and a recent $\tilde {\mathcal{O}}(n + {k^{3. 5}} \cdot n/m)$-time solution by Charalampopoulos, Kociumaka, and Wellnitz [FOCS'22]. In this work, we examine whether these results can be lifted to PMWWE even though (1) the underlying algorithms rely on combinatorial properties specific to the unweighted edit distance, and (2) under standard fine-grained complexity assumptions, computing the weighted edit distance is strictly harder than computing the unweighted edit distance [Cassis, Kociumaka, and Wellnitz; FOCS'23]. We obtain three main results: •a conceptually simple $\tilde {\mathcal{O}}\left( {nk} \right)$-time algorithm for PMWWE, very different from that of Landau and Vishkin; •a significantly more complicated $\tilde {\mathcal{O}}(n + {k^{3. 5}} \cdot {W^4} \cdot n/m)$ time algorithm for PMWWE under the assumption that the weight function is a metric with integer values between 0 and W; and•an $\tilde {\mathcal{O}}(n + {k^4} \cdot n/m)$-time algorithm for PMWWE for the case of arbitrary weights. In the setting of metrics with small integer values, we nearly match the state of the art for PMwE where W=1.

STOC Conference 2024 Conference Paper

Counting Small Induced Subgraphs with Edge-Monotone Properties

• Simon Döring
• Dániel Marx
• Philip Wellnitz

STOC Conference 2024 Conference Paper

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- n string T (the text), a length- m string P (the pattern), and a positive integer k (the threshold), asks to list all fragments of T that are at edit distance at most k from P . The one-way communication complexity of this problem is the minimum amount of space needed to encode the answer so that it can be retrieved without accessing the input strings P and T . The closely related Pattern Matching with Mismatches problem (defined in terms of the Hamming distance instead of the edit distance) is already well understood from the communication complexity perspective: Clifford, Kociumaka, and Porat [SODA 2019] proved that Ω( n / m · k log( m / k )) bits are necessary and O ( n / m · k log( m |Σ|/ k )) bits are sufficient; the upper bound allows encoding not only the occurrences of P in T with at most k mismatches but also the substitutions needed to make each k -mismatch occurrence exact. Despite recent improvements in the running time [Charalampopoulos, Kociumaka, and Wellnitz; FOCS 2020 and 2022], the communication complexity of Pattern Matching with Edits remained unexplored, with a lower bound of Ω( n / m · k log( m / k )) bits and an upper bound of O ( n / m · k 3 log m ) bits stemming from previous research. In this work, we prove an upper bound of O ( n / m · k log 2 m ) bits, thus establishing the optimal communication complexity up to logarithmic factors. We also show that O ( n / m · k log m log( m |Σ|)) bits allow encoding, for each k -error occurrence of P in T , the shortest sequence of edits needed to make the occurrence exact. Our result further emphasizes the close relationship between Pattern Matching with Mismatches and Pattern Matching with Edits. We leverage the techniques behind our new result on the communication complexity to obtain quantum algorithms for Pattern Matching with Edits: we demonstrate a quantum algorithm that uses O ( n 1+ o (1) / m · √ km ) queries and O ( n 1+ o (1) / m · (√ k m + k 3.5 )) quantum time. Moreover, when determining the existence of at least one occurrence, the algorithm uses O (√ n 1+ o (1) / m · √ km ) queries and O (√ n 1+ o (1) / m · (√ k m + k 3.5 )) time. For both cases, we establish corresponding lower bounds to demonstrate that the query complexity is optimal up to sub-polynomial factors.

FOCS Conference 2023 Conference Paper

Optimal Algorithms for Bounded Weighted Edit Distance

• Alejandro Cassis
• Tomasz Kociumaka
• Philip Wellnitz

The edit distance (also known as Levenshtein 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-programming algorithm computes the edit distance of two length- n strings in $\mathcal{O}\left(n^{2}\right)$ time, which is optimal up to subpolynomial factors assuming the Strong Exponential Time Hypothesis (SETH). An established way of circumventing this hardness is to consider the bounded setting, where the running time is parameterized by the edit distance k. A celebrated algorithm by Landau and Vishkin (JCSS’88) achieves a running time of $\mathcal{O}\left(n+k^{2}\right)$, which is optimal as a function of n and k (again, up to subpolynmial factors and assuming SETH). While the theory community thoroughly studied the Levenshtein distance, most practical applications rely on a more general weighted edit distance, where each edit has a weight depending on its type and the involved characters from the alphabet $\Sigma$. This is formalized through a weight function $w: \Sigma \cup\{\varepsilon\} \times \Sigma \cup\{\varepsilon\} \rightarrow \mathbb{R}$ normalized so that $w(a \mapsto a)=0$ for $a \in \Sigma \cup\{\varepsilon\}$ and $w(a \mapsto b) \geq 1$ for $a, b \in \Sigma \cup\{\varepsilon\}$ with $a \neq b$; the goal is to find an alignment of the two strings minimizing the total weight of edits. The classic $\mathcal{O}\left(n^{2}\right)$-time algorithm supports this setting seamlessly, but for many decades just a straightforward $\mathcal{O}(n k)$-time solution was known for the bounded version of the weighted edit distance problem. Only very recently, Das, Gilbert, Hajiaghayi, Kociumaka, and Saha (STOC’23) gave the first non-trivial algorithm, achieving a time complexity of $\mathcal{O}\left(n+k^{5}\right)$. While this running time is linear for $k \leq n^{1 / 5}$, it is still very far from $\mathcal{O}\left(n+k^{2}\right)$-the bound achievable in the unweighted setting. This is unsatisfactory, especially given the lack of any compelling evidence that the weighted version is inherently harder. In this paper, we essentially close this gap by showing both an improved $\widetilde{\mathcal{O}}\left(n+\sqrt{n k^{3}}\right)$-time algorithm and, more surprisingly, a matching lower bound: Conditioned on the All-Pairs Shortest Paths (APSP) hypothesis, the running time of our solution is optimal for $\sqrt{n} \leq k \leq n$ (up to subpolynomial factors). In particular, this is the first separation between the complexity of the weighted and unweighted edit distance problems. Just like the Landau-Vishkin algorithm, our algorithm can be adapted to a wide variety of settings, such as when the input is given in a compressed representation. This is because, independently of the string length n, our procedure takes $\widetilde{\mathcal{O}}\left(k^{3}\right)$ time assuming that the equality of any two substrings can be tested in $\widetilde{\mathcal{O}}(1)$ time. Consistently with the previous work, our algorithm relies on the observation that strings with a rich structure of low-weight alignments must contain highly repetitive substrings. Nevertheless, achieving the optimal running time requires multiple new insights. We capture the right notion of repetitiveness using a tailor-made compressibility measure that we call self-edit distance. Our divide-and-conquer algorithm reduces the computation of weighted edit distance to several subproblems involving substrings of small self-edit distance and, at the same time, distributes the budget for edit weights among these subproblems. We then exploit the repetitive structure of the underlying substrings using state-of-the-art results for multiple-source shortest paths in planar graphs (Klein, SODA’05). As a stepping stone for our conditional lower bound, we study a dynamic problem of maintaining two strings subject to updates (substitutions of characters) and weighted edit distance queries. We significantly extend the construction of Abboud and Dahlgaard (FOCS’16), originally for dynamic shortest paths in planar graphs, to show that a sequence of n updates and $q \leq n$ queries cannot be handled much faster than in $\mathcal{O}\left(n^{2} \sqrt{q}\right)$ time. We then compose the snapshots of the dynamic strings to derive hardness of the static problem in the bounded setting.

SODA Conference 2023 Conference Paper

Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs

• Jacob Focke
• Dániel Marx
• Fionn Mc Inerney
• Daniel Neuen
• Govind S. Sankar
• Philipp Schepper
• Philip Wellnitz

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 of a graph G is a set S of vertices such that | N ( u ) ∩ S | ∈ σ for every u ∈ S, and | N ( v ) ∩ S | ∈ ρ for every v ∉ S. The problem of finding a (σ, ρ)-set (of a certain size) unifies standard problems such as INDEPENDENT SET, DOMINATING SET, INDEPENDENT DOMINATING SET, and many others. For all pairs of finite or cofinite sets (σ, ρ), we determine (under standard complexity assumptions) the best possible value c σ, ρ such that there is an algorithm that counts (σ, ρ)-sets in time c tw σ, ρ · n O(1) (if a tree decomposition of width tw is given in the input). Let s top denote the largest element of σ if σ is finite, or the largest missing integer +1 if σ is cofinite; r top is defined analogously for ρ. Surprisingly, c σ, ρ is often significantly smaller than the natural bound s top + r top + 2 achieved by existing algorithms [van Rooij, 2020]. Toward defining c σ, ρ, we say that (σ, ρ) is m -structured if there is a pair (α, β) such that every integer in σ equals α mod m, and every integer in ρ equals β mod m. Then, setting • c σ, ρ = s top + r top +2 if (σ, ρ) is not m-structured for any m ≥ 2 • c σ, ρ = max{ s top, r top } + 2 if (σ, ρ) is 2-structured, but not m-structured for any m ≥ 3, and s top = r top is even, and • c σ, ρ = max{ s top, r top } + 1, otherwise we provide algorithms counting (σ, ρ)-sets in time c tw σ, ρ · n O(1). For example, for the EXACT INDEPENDENT DOMINATING SET problem (also known as PERFECT CODE) corresponding to σ = {0} and ρ = {1}, this improves the 3 tw · n O(1) algorithm of van Rooij to 2 tw · n O(1). Despite the unusually delicate definition of c σ, ρ, we show that our algorithms are most likely optimal, i. e. , for any pair (σ, ρ) of finite or cofinite sets where the problem is non-trivial, and any ε > 0, a ( c σ, ρ — ε) tw · n O(1) - algorithm counting the number of (σ, ρ)-sets would violate the COUNTING STRONG EXPONENTIAL-TIME HYPOTHESIS (#SETH). For finite sets σ and ρ, our lower bounds also extend to the decision version, showing that our algorithms are optimal in this setting as well. In contrast, for many cofinite sets, we show that further significant improvements for the decision and optimization versions are possible using the technique of representative sets. * The full version of this work can be accessed at https: //arxiv. org/abs/2211. 04278. Research supported by the European Research Council (ERC) consolidator grant No. 725978 SYSTEMATICGRAPH.

FOCS Conference 2022 Conference Paper

Faster Pattern Matching under Edit Distance: A Reduction to Dynamic Puzzle Matching and the Seaweed Monoid of Permutation Matrices

• Panagiotis Charalampopoulos
• Tomasz Kociumaka
• Philip Wellnitz

We consider the approximate pattern matching problem under the edit distance. Given a text T of length n, a pattern P of length m, and a threshold k, the task is to find the starting positions of all substrings of T that can be transformed to P with at most k edits. More than 20 years ago, Cole and Hariharan [SODA’98, J. Comput. ’02] gave an $\mathcal{O}(n+k^{4}\cdot n/m)$ time algorithm for this classic problem, and this runtime has not been improved since. Here, we present an algorithm that runs in time $\mathcal{O}\left(n+ k^{3. 5}\sqrt{\log m\log k}\cdot n/m\right)$, thus breaking through this longstanding barrier. In the case where $n^{1/4+\varepsilon}\leq k\leq n^{2/5-\varepsilon}$ for some arbitrarily small positive constant $\varepsilon$, our algorithm improves over the state-of-the-art by polynomial factors: it is polynomially faster than both the algorithm of Cole and Hariharan and the classic $\mathcal{O}(kn)$-time algorithm of Landau and Vishkin [STOC’86, J. Algorithms’89]. We observe that the bottleneck case of the alternative $\mathcal{O}(n+k^4 \cdot n / m$-time algorithm of Charalampopoulos, Kociumaka, and Wellnitz [FOCS’20] is when the text and the pattern are (almost) periodic. Our new algorithm reduces this case to a new Dynamic Puzzle Matching problem, which we solve by building on tools developed by Tiskin [SODA’10, Algorithmica’15] for the so-called seaweed monoid of permutation matrices. Our algorithm relies only on a small set of primitive operations on strings and thus also applies to the fully-compressed setting (where text and pattern are given as straight-line programs) and to the dynamic setting (where we maintain a collection of strings under creation, splitting, and concatenation), improving over the state of the art.

SODA Conference 2021 Conference Paper

On Near-Linear-Time Algorithms for Dense Subset Sum

• Karl Bringmann
• Philip Wellnitz

In the Subset Sum problem we are given a set of n positive integers X and a target t and are asked whether some subset of X sums to t. Natural parameters for this problem that have been studied in the literature are n and t as well as the maximum input number mx x and the sum of all input numbers Σ x. In this paper we study the dense case of Subset Sum, where all these parameters are polynomial in n. In this regime, standard pseudo-polynomial algorithms solve Subset Sum in polynomial time n O (1). Our main question is: When can dense Subset Sum be solved in near-linear time Õ ( n )? We provide an essentially complete dichotomy by designing improved algorithms and proving conditional lower bounds, thereby determining essentially all settings of the parameters n, t, mx x, Σ x for which dense Subset Sum is in time Õ ( n ). For notational convenience we assume without loss of generality that t ≥ mx x (as larger numbers can be ignored) and t ≤ Σ x /2 (using symmetry). Then our dichotomy reads as follows: • By reviving and improving an additive-combinatorics-based approach by Galil and Margalit [SICOMP'91], we show that Subset Sum is in near-linear time Õ ( n ) if t » mx x Σ x / n 2. • We prove a matching conditional lower bound: If Subset Sum is in near-linear time for any setting with t « mx x Σ x / n 2, then the Strong Exponential Time Hypothesis and the Strong k-Sum Hypothesis fail. We also generalize our algorithm from sets to multi-sets, albeit with non-matching upper and lower bounds.

SODA Conference 2020 Conference Paper

Counting and Finding Homomorphisms is Universal for Parameterized Complexity Theory

• Marc Roth
• Philip Wellnitz

Counting homomorphisms from a graph H into another graph G is a fundamental problem of (parameterized) counting complexity theory. In this work, we study the case where both graphs H and G stem from given classes of graphs: H ϵ and G ϵ. By this, we combine the structurally restricted version of this problem (where the class = ┬ is the set of all graphs), with the language-restricted version (where the class = ┬ is the set of all graphs). The structurally restricted version allows an exhaustive complexity classification for classes: Either we can count all homomorphisms in polynomial time (if the treewidth of is bounded), or the problem becomes #W[1]-hard [Dalmau, Jonsson, Th. Comp. Sci’04]. In contrast, in this work, we show that the combined view most likely does not admit such a complexity dichotomy. Our main result is a construction based on Kneser graphs that associates every problem P in #W[1] with two classes of graphs and such that the problem P is equivalent to the problem #H om ( → ) of counting homomorphisms from a graph in to a graph in. In view of Ladner's seminal work on the existence of NP-intermediate problems [J. ACM’75] and its adaptations to the parameterized setting, a classification of the class #W[1] in fixed-parameter tractable and #W[1]-complete cases is unlikely. Hence, obtaining a complete classification for the problem #H om ( → ) seems unlikely. Further, our proofs easily adapt to W[1] and the problem of deciding whether a homomorphism between graphs exists. In search of complexity dichotomies, we hence turn to special graph classes. Those classes include line graphs, claw-free graphs, perfect graphs, and combinations thereof, and F -colorable graphs for fixed graphs F. As a special case, we obtain an easy proof of the parameterized intractability result of the problem of counting k -matchings in bipartite graphs.

FOCS Conference 2020 Conference Paper

Counting Small Induced Subgraphs Satisfying Monotone Properties

• Marc Roth
• Johannes Schmitt 0002
• Philip Wellnitz

Given a graph property Φ, we study the problem #INDSUB(Φ) which asks, on input a graph G and a positive integer k, to compute the number # IndSub(Φ, k→ G) of induced subgraphs of size k in G that satisfy Φ. The search for explicit criteria on Φ ensuring that # INDSUB(Φ) is hard was initiated by Jerrum and Meeks [J. Comput. Syst. Sci. 15] and is part of the major line of research on counting small patterns in graphs. However, apart from an implicit result due to Curticapean, Dell and Marx [STOC 17] proving that a full classification into “easy” and “hard” properties is possible and some partial results on edge-monotone properties due to Meeks [Discret. Appl. Math. 16] and Dörfler et al. [MFCS 19], not much is known. In this work, we fully answer and explicitly classify the case of monotone, that is subgraph-closed, properties: We show that for any non-trivial monotone property Φ, the problem #INDSUB(Φ) cannot be solved in time f(k). |V(G)| o(k/log1/2 (k)) for any function f, unless the Exponential Time Hypothesis fails. By this, we establish that any significant improvement over the brute-force approach is unlikely; in the language of parameterized complexity, we also obtain a #W[1] - completeness result.

FOCS Conference 2020 Conference Paper

Faster Approximate Pattern Matching: A Unified Approach

• Panagiotis Charalampopoulos
• Tomasz Kociumaka
• Philip Wellnitz

In the approximate pattern matching problem, given a text T, a pattern P, and a threshold k, the task is to find (the starting positions of) all substrings of T that are at distance at most k from P. We consider the two most fundamental string metrics: Under the Hamming distance, we search for substrings of T that have at most k mismatches with P, while under the edit distance, we search for substrings of T that can be transformed to P with at most k edits. Exact occurrences of P in T have a very simple structure: If we assume for simplicity that |P| 2 ) k-mismatch occurrences of P in T, or both P and T are at Hamming distance O(k) from strings with a common string period of length O(m/k). We tighten this characterization by showing that there are O(k) k-mismatch occurrences in the non-periodic case, and we lift it to the edit distance setting, where we tightly bound the number of k-edit occurrences by O(k 2 ) in the non-periodic case. Our proofs are constructive and let us obtain a unified framework for approximate pattern matching for both considered distances. In particular, we provide meta-algorithms that only rely on a small set of primitive operations. We showcase the generality of our meta-algorithms with results for the fully compressed setting, the dynamic setting, and the standard setting.

MFCS Conference 2019 Conference Paper

Counting Induced Subgraphs: An Algebraic Approach to #W[1]-hardness

• Julian Dörfler
• Marc Roth
• Johannes Schmitt 0002
• Philip Wellnitz

We study the problem #IndSub(Phi) of counting all induced subgraphs of size k in a graph G that satisfy the property Phi. This problem was introduced by Jerrum and Meeks and shown to be #W[1]-hard when parameterized by k for some families of properties Phi including, among others, connectivity [JCSS 15] and even- or oddness of the number of edges [Combinatorica 17]. Very recently [IPEC 18], two of the authors introduced a novel technique for the complexity analysis of #IndSub(Phi), inspired by the "topological approach to evasiveness" of Kahn, Saks and Sturtevant [FOCS 83] and the framework of graph motif parameters due to Curticapean, Dell and Marx [STOC 17], allowing them to prove hardness of a wide range of properties Phi. In this work, we refine this technique for graph properties that are non-trivial on edge-transitive graphs with a prime power number of edges. In particular, we fully classify the case of monotone bipartite graph properties: It is shown that, given any graph property Phi that is closed under the removal of vertices and edges, and that is non-trivial for bipartite graphs, the problem #IndSub(Phi) is #W[1]-hard and cannot be solved in time f(k)* n^{o(k)} for any computable function f, unless the Exponential Time Hypothesis fails. This holds true even if the input graph is restricted to be bipartite and counting is done modulo a fixed prime. A similar result is shown for properties that are closed under the removal of edges only.

SODA Conference 2019 Conference Paper

Few Matches or Almost Periodicity: Faster Pattern Matching with Mismatches in Compressed Texts

• Karl Bringmann
• Marvin Künnemann
• Philip Wellnitz

A fundamental problem on strings in the realm of approximate string matching is pattern matching with mismatches: Given a text t, a pattern p, and a number k, determine whether some substring of t has Hamming distance at most k to p; such a substring is called a k-match. As real-world texts often come in compressed form, we study the case of searching for a small pattern p in a text t that is compressed by a straight-line program. This grammar compression is popular in the string community, since it is mathematically elegant and unifies many practically relevant compression schemes such as the Lempel-Ziv family, dictionary methods, and others. We denote by m the length of p and by n the compressed size of t. While exact pattern matching, that is, the case k = 0, is known to be solvable in near-linear time Õ ( n + m ) [Jeż TALG’15], despite considerable interest in the string community, the fastest known algorithm for pattern matching with mismatches runs in time [Gawrychowski, Straszak ISAAC’13], which is far from linear even for very small k. In this paper, we obtain an algorithm for pattern matching with mismatches running in time Õ (( n + m ) poly( k )). This is near-linear in the input size for any constant (or slightly superconstant) k. We obtain analogous running time for counting and enumerating all k -matches. Our algorithm is based on a new structural insight for approximate pattern matching, essentially showing that either the number of k -matches is very small or both text and pattern must be almost periodic. While intuitive and simple for exact matches, such a characterization is surprising when allowing k mismatches.