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 the k-error occurrences of P in T, that is, all fragments of T whose edit distance to P is at most k. The one-way communication complexity of this problem is the minimum number of bits that Alice, given an instance (P,T,k) of the problem, must send to Bob so that Bob can reconstruct the answer solely from that message. In recent work [STOC'24], we showed that, in the natural parameter regime 0 < k < m < n/2, Ω(n/m ⋅ k log(m/k)) bits are necessary and 𝒪(n/m ⋅ k log² m) bits are sufficient for this problem. More generally, for strings over an alphabet Σ, we gave an 𝒪(n/m ⋅ k log m log(m|Σ|))-bit encoding that allows one to recover a shortest sequence of edits for every k-error occurrence of P in T. In this paper, we revisit the original proof and improve the encoding size to 𝒪(n/m ⋅ k log (m|Σ|/k)), which matches the lower bound for constant-sized alphabets. We further establish a new tight lower bound of Ω(n/m ⋅ k log(m|Σ|/k)) for the edit sequence reporting variant we solve. Our encoding size also matches the communication complexity established for the simpler Pattern Matching with Mismatches problem in the context of streaming algorithms [Clifford, Kociumaka, Porat; SODA'19].

Subgraph counting is a fundamental and well-studied problem whose computational complexity is well understood. Quite surprisingly, the hypergraph version of subgraph counting has been almost ignored. In this work, we address this gap by investigating the most basic sub-hypergraph counting problem: given two hypergraphs \(H\) and \(G\), compute the number of sub-hypergraphs of \(G\) isomorphic to \(H\). Formally, for a family \(\mathcal{H}\) of hypergraphs, let #Sub\((\mathcal{H})\) be the restriction of the problem to \(H \in \mathcal{H}\); the induced variant #IndSub\((\mathcal{H})\) is defined analogously. Our main contribution is a complete classification of the fixed-parameter tractability of these problems. Assuming the Exponential Time Hypothesis, we prove that #Sub\((\mathcal{H})\) is fixed-parameter tractable if and only if \(\mathcal{H}\) has bounded fractional co-independent edge-cover number, a novel graph parameter introduced in this work, and that #IndSub\((\mathcal{H})\) is fixed-parameter tractable if and only if \(\mathcal{H}\) has bounded fractional edge-cover number. Both results subsume pre-existing results for graphs as special cases. We also show that the fixed-parameter tractable cases of #Sub\(\mathcal{H})\) and #IndSub\((\mathcal{H})\) are unlikely to be in polynomial time, unless respectively \(\#P = P\) and Graph Isomorphism \(\in\, P\). This shows a separation with the special case of graphs, where the fixed-parameter tractable cases are known to actually be in polynomial time. From a technical standpoint, we turn to the hypergraph homomorphism basis and lift the complexity monotonicity principle due to Curticapean, Dell, and Marx [STOC 2017] from graphs to hypergraphs of unbounded rank. Moreover, we crucially rely on the integrality gap for fractional independent sets based on adaptive width due to Bressan, Lanzinger, and Roth [STOC 2023]. The heart of our proofs consists of a careful investigation of the adaptive width of the patterns that survive in the hypergraph homomorphism basis. We also consider a natural variant of sub-hypergraphs where edges are trimmed to be vertex subsets; we show that, surprisingly, in this case complexity monotonicity fails.

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.

A graph property is a function Φ that maps every graph to {0,1} and is invariant under isomorphism. In the #IndSub(Φ) problem, given a graph G and an integer k, the task is to count the number of k-vertex induced subgraphs G’ with Φ(G’ ) = 1. For example, this problem family includes counting k-cliques or induced k vertex subgraphs that are connected, among others. There has been extensive work on determining the parameterized complexity of #IndSub(Φ) for various properties Φ. Very recently, Döring, Marx, and Wellnitz [STOC 2024] showed the general result that #IndSub(Φ) is #W[1]-hard for every nontrivial edge-monotone property Φ and, assuming ETH, cannot be solved in time f (k ) no (log k ).

Approximate Pattern Matching is among the most fundamental string-processing tasks. Given a text T of length n, a pattern P of length m, and a threshold k, the task is to identify the fragments of T that are at distance at most k to P. We consider the two most common distances: Hamming distance (the number of mismatches or character substitutions) in Pattern Matching with Mismatches and edit distance (the minimum number of character insertions, deletions, and substitutions) in Pattern Matching with Edits. We revisit the complexity of these two problems in the quantum setting.

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 that, for every selected vertex, the number of selected neighbors is in $σ$ and, for every unselected vertex, the number of selected neighbors is in $ρ$ [Telle, Nord. J. Comp. 1994]. This framework covers many fundamental graph problems such as Independent Set and Dominating Set. We significantly extend the recent result by Focke et al. [SODA 2023] to investigate the case when $σ$ and $ρ$ are two (potentially different) residue classes modulo $m\ge 2$. We study the problem parameterized by treewidth and present an algorithm that solves in time $m^{tw} \cdot n^{O(1)}$ the decision, minimization and maximization version of the problem. This significantly improves upon the known algorithms where for the case $m \ge 3$ not even an explicit running time is known. We complement our algorithm by providing matching lower bounds which state that there is no $(m-ε)^{pw} \cdot n^{O(1)}$-time algorithm parameterized by pathwidth $pw$, unless SETH fails. For $m = 2$, we extend these bounds to the minimization version as the decision version is efficiently solvable.

We investigate how efficiently a well-studied family of domination-type problems can be solved on bounded-treewidth graphs. For sets \(\sigma,\rho\) of non-negative integers, a \((\sigma,\rho)\) -set of a graph G is a set S of vertices such that \(|N(u)\cap S|\in\sigma\) for every \(u\in S\) , and \(|N(\!\textit{v})\cap S|\in\rho\) for every \(\textit{v}\not\in S\) . The problem of finding a \((\sigma,\rho)\) -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 \((\sigma,\rho)\) , we determine (under standard complexity assumptions) the best possible value \(c_{\sigma,\rho}\) such that there is an algorithm that counts \((\sigma,\rho)\) -sets in time \(c_{\sigma,\rho}^{\textsf{tw}}\cdot n^{O(1)}\) (if a tree decomposition of width \(\textsf{tw}\) is given in the input). Let \(s_{{\rm top}}\) denote the largest element of \(\sigma\) if \(\sigma\) is finite, or the largest missing integer \(+1\) if \(\sigma\) is cofinite; \(r_{{\rm top}}\) is defined analogously for \(\rho\) . Surprisingly, \(c_{\sigma,\rho}\) is often significantly smaller than the natural bound \(s_{{\rm top}}+r_{{\rm top}}+2\) achieved by existing algorithms. Toward defining \(c_{\sigma,\rho}\) , we say that \((\sigma,\rho)\) is \({\mathrm{m}}\) -structured if there is a pair \((\alpha,\beta)\) such that every integer in \(\sigma\) equals \(\alpha\) mod \({\mathrm{m}}\) , and every integer in \(\rho\) equals \(\beta\) mod \({\mathrm{m}}\) . Then, setting — \(c_{\sigma,\rho}=s_{{\rm top}}+r_{{\rm top}}+2\) if \((\sigma,\rho)\) is not \({\mathrm{m}}\) -structured for any \({\mathrm{m}}\geq 2\) , — \(c_{\sigma,\rho}=\max\{s_{{\rm top}},r_{{\rm top}}\}+2\) if \((\sigma,\rho)\) is 2-structured, but not \({\mathrm{m}}\) -structured for any \({\mathrm{m}}\geq 3\) , and

We study the parameterized complexity of #IndSub(Φ), where given a graph G and an integer k, the task is to count the number of induced subgraphs on k vertices that satisfy the graph property Φ. Focke and Roth [STOC 2022] completely characterized the complexity for each Φ that is a hereditary property (that is, closed under vertex deletions): #IndSub(Φ) is #W[1]-hard except in the degenerate cases when every graph satisfies Φ or only finitely many graphs satisfy Φ. We complement this result with a classification for each Φ that is edge-monotone (that is, closed under edge deletions): #IndSub(Φ) is #W[1]-hard except in the degenerate case when there are only finitely many integers k such that Φ is nontrivial on k-vertex graphs. Our result generalizes earlier results for specific properties Φ that are related to the connectivity or density of the graph. Further, we extend the #W[1]-hardness result by a lower bound which shows that #IndSub(Φ) cannot be solved in time f(k) · |V(G)|o(√logk / loglogk) for any function f, unless the Exponential-Time Hypothesis (ETH) fails. For many natural properties, we obtain even a tight bound f(k) · |V(G)|o(k); for example, this is the case for every property Φ that is nontrivial on k-vertex graphs for each k greater than some k0.

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.

Given a graph property [Formula: see text], the problem [Formula: see text] asks, on input of a graph [Formula: see text] and a positive integer [Formula: see text], to compute the number [Formula: see text] of induced subgraphs of size [Formula: see text] in [Formula: see text] that satisfy [Formula: see text]. The search for explicit criteria on [Formula: see text] ensuring that [Formula: see text] is hard was initiated by Jerrum and Meeks [ J. Comput. System Sci., 81 (2015), pp. 702–716] 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, ACM, New York, pp. 151–158] proving that a full classification into “easy” and “hard” properties is possible and some partial results on edge-monotone properties due to Meeks [ Discrete Appl. Math., 198 (2016), pp. 170–194] and Dörfler et al. [ MFCS, LIPIcs Leibniz Int. Proc. Inform. 138, Wadern Germany, 2019, 26], 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 nontrivial monotone property [Formula: see text], the problem [Formula: see text] cannot be solved in time [Formula: see text] for any function [Formula: see text], 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 [Formula: see text]-completeness result. The methods we develop for the above problem also allow us to prove a conjecture by Jerrum and Meeks [ ACM Trans. Comput. Theory, 7 (2015), 11; Combinatorica 37 (2017), pp. 965–990]: [Formula: see text] is [Formula: see text]-complete if [Formula: see text] is a nontrivial graph property only depending on the number of edges of the graph.

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.

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 ctwσ,ρ · nO(1) (if a tree decomposition of width tw is given in the input). Let stop denote the largest element of σ if σ is finite, or the largest missing integer +1 if σ is cofinite; rtop is defined analogously for ρ. Surprisingly, cσ,ρ is often significantly smaller than the natural bound stop + rtop + 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σ,ρ = stop + rtop +2 if (σ, ρ) is not m-structured for any m ≥ 2 • cσ,ρ = max{stop,rtop} + 2 if (σ,ρ) is 2-structured, but not m-structured for any m ≥ 3, and stop = rtop is even, and • cσ,ρ = max{stop, rtop} + 1, otherwise we provide algorithms counting (σ, ρ)-sets in time ctwσ,ρ · nO(1). For example, for the EXACT INDEPENDENT DOMINATING SET problem (also known as PERFECT CODE) corresponding to σ = {0} and ρ = {1}, this improves the 3tw · nO(1) algorithm of van Rooij to 2tw· nO(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 · nO(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.

Abstract. Given a graph property [Formula: see text], we consider the problem [Formula: see text] EdgeSub [Formula: see text], where the input is a pair of a graph [Formula: see text] and a positive integer [Formula: see text], and the task is to compute the number of [Formula: see text]-edge subgraphs in [Formula: see text] that satisfy [Formula: see text]. Specifically, we study the parameterized complexity of [Formula: see text] EdgeSub [Formula: see text] with respect to both approximate and exact counting, as well as its decision version EdgeSub [Formula: see text]. Among others, our main result fully resolves the case of minor-closed properties [Formula: see text]: the decision problem EdgeSub [Formula: see text] always admits a fixed-parameter tractable algorithm, and the counting problem [Formula: see text] EdgeSub [Formula: see text] always admits a fixed-parameter tractable randomized approximation scheme. For exact counting, we present an exhaustive and explicit criterion on the property [Formula: see text] which, if satisfied, yields fixed-parameter tractability and otherwise [Formula: see text]-hardness. Additionally, our hardness results come with an almost tight conditional lower bound under the exponential time hypothesis. Our main technical result concerns the exact counting problem: Building upon the breakthrough result of Curticapean, Dell, and Marx (Symposium on Theory of Computing 2017), we express the number of subgraphs satisfying [Formula: see text] as a finite linear combination of graph homomorphism counts and derive the complexity of computing this number by studying its coefficients. Our approach relies on novel constructions of low-degree Cayley graph expanders of [Formula: see text]-groups, which might be of independent interest. The properties of those expanders allow us to analyze the coefficients in the aforementioned linear combinations over the field [Formula: see text] which gives us significantly more control over the cancelation behavior of the coefficients.

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.

This paper is concerned with the \(1|| \sum p_j U_j\) problem, the problem of minimizing the total processing time of tardy jobs on a single machine. This is not only a fundamental scheduling problem, but also an important problem from a theoretical point of view as it generalizes the Subset Sum problem and is closely related to the 0/1-Knapsack problem. The problem is well-known to be NP-hard, but only in a weak sense, meaning it admits pseudo-polynomial time algorithms. The best known running time follows from the famous Lawler and Moore algorithm that solves a more general weighted version in \(O(P \cdot n)\) time, where P is the total processing time of all n jobs in the input. This algorithm has been developed in the late 60s, and has yet to be improved to date. In this paper we develop two new algorithms for problem, each improving on Lawler and Moore’s algorithm in a different scenario. Our first algorithm runs in \({\tilde{O}}(P^{7/4})\) time, and outperforms Lawler and Moore’s algorithm in instances where \(n={\tilde{\omega }}(P^{3/4})\) . Our second algorithm runs in \({\tilde{O}}(\min \{P \cdot D_{\#}, P + D\})\) time, where \(D_{\#}\) is the number of different due dates in the instance, and D is the sum of all different due dates. This algorithm improves on Lawler and Moore’s algorithm when \(n={\tilde{\omega }}(D_{\#})\) or \(n={\tilde{\omega }}(D/P)\) . Further, it extends the known \({\tilde{O}}(P)\) algorithm for the single due date special case of \(1||\sum p_jU_j\) in a natural way. Both algorithms rely on basic primitive operations between sets of integers and vectors of integers for the speedup in their running times. The second algorithm relies on fast polynomial multiplication as its main engine, and can be easily extended to the case of a fixed number of machines. For the first algorithm we define a new “skewed” version of \((\max ,\min )\) -Convolution which is interesting in its own right.

Abstract We study the problem $$\#\textsc {IndSub}(\varPhi )$$ # I N D S U B ( Φ ) of counting all induced subgraphs of size k in a graph G that satisfy the property $$\varPhi $$ Φ . It is shown that, given any graph property $$\varPhi $$ Φ that distinguishes independent sets from bicliques, $$\#\textsc {IndSub}(\varPhi )$$ # I N D S U B ( Φ ) is hard for the class $$\#\mathsf {W[1]}$$ # W [ 1 ] , i.e., the parameterized counting equivalent of $${{\mathsf {N}}}{{\mathsf {P}}}$$ N P . Under additional suitable density conditions on $$\varPhi $$ Φ , satisfied e.g. by non-trivial monotone properties on bipartite graphs, we strengthen $$\#\mathsf {W[1]}$$ # W [ 1 ] -hardness by establishing that $$\#\textsc {IndSub}(\varPhi )$$ # I N D S U B ( Φ ) cannot be solved in time $$f(k)\cdot n^{o(k)}$$ f ( k ) · n o ( k ) for any computable function f, unless the Exponential Time Hypothesis fails. Finally, we observe that our results remain true even if the input graph G is restricted to be bipartite and counting is done modulo a fixed prime.

Given a graph property $Φ$, we consider the problem $\mathtt{EdgeSub}(Φ)$, where the input is a pair of a graph $G$ and a positive integer $k$, and the task is to decide whether $G$ contains a $k$-edge subgraph that satisfies $Φ$. Specifically, we study the parameterized complexity of $\mathtt{EdgeSub}(Φ)$ and of its counting problem $\#\mathtt{EdgeSub}(Φ)$ with respect to both approximate and exact counting. We obtain a complete picture for minor-closed properties $Φ$: the decision problem $\mathtt{EdgeSub}(Φ)$ always admits an FPT algorithm and the counting problem $\#\mathtt{EdgeSub}(Φ)$ always admits an FPTRAS. For exact counting, we present an exhaustive and explicit criterion on the property $Φ$ which, if satisfied, yields fixed-parameter tractability and otherwise $\#\mathsf{W[1]}$-hardness. Additionally, most of our hardness results come with an almost tight conditional lower bound under the so-called Exponential Time Hypothesis, ruling out algorithms for $\#\mathtt{EdgeSub}(Φ)$ that run in time $f(k)\cdot|G|^{o(k/\log k)}$ for any computable function $f$. As a main technical result, we gain a complete understanding of the coefficients of toroidal grids and selected Cayley graph expanders in the homomorphism basis of $\#\mathtt{EdgeSub}(Φ)$. This allows us to establish hardness of exact counting using the Complexity Monotonicity framework due to Curticapean, Dell and Marx (STOC'17). Our methods can also be applied to a parameterized variant of the Tutte Polynomial $T^k_G$ of a graph $G$, to which many known combinatorial interpretations of values of the (classical) Tutte Polynomial can be extended. As an example, $T^k_G(2,1)$ corresponds to the number of $k$-forests in the graph $G$. Our techniques allow us to completely understand the parametrized complexity of computing the evaluation of $T^k_G$ at every pair of rational coordinates $(x,y)$.

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 mxx 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 nO(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 ≥ mxx (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 » mxxΣx/n2. We prove a matching conditional lower bound: If Subset Sum is in near-linear time for any setting with t « mxxΣx/n2, 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.

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(k2) 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.

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.

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 #Hom( → ) 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 #Hom( → ) 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.

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 than enumerating them. In particular, we are interested in the problem’s parameterized and data complexity, where the query is considered to be small or even fixed, and the database is considered to be large. We identify two structural parameters for conjunctive queries that capture their inherent complexity: The dominating star size and the linked matching number. If the dominating star size of a conjunctive query is large, then we show that counting solution tuples to the query is at least as hard as counting dominating sets, which yields a fine-grained complexity lower bound under the Strong Exponential Time Hypothesis (SETH) as well as a #W[2]-hardness result in parameterized complexity. Moreover, if the linked matching number of a conjunctive query is large, then we show that the structure of the query is so rich that arbitrary queries up to a certain size can be encoded into it; in the language of parameterized complexity, this essentially establishes a #A[2]-completeness result. Using ideas stemming from Lovász (1967), we lift complexity results from the class of conjunctive queries to arbitrary existential or universal formulas that might contain inequalities and negations on constraints over the free variables. As a consequence, we obtain a complexity classification that refines and generalizes previous results of Chen, Durand, and Mengel (ToCS 2015; ICDT 2015; PODS 2016) for conjunctive queries and of Curticapean and Marx (FOCS 2014) for the subgraph counting problem. Our proof also relies on graph minors, and we show a strengthening of the Excluded-Grid-Theorem which might be of independent interest: If the linked matching number (and thus the treewidth) is large, then not only can we find a large grid somewhere in the graph, but we can find a large grid whose diagonal has disjoint paths leading into an assumed node-well-linked set.

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.

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.

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-adjoining grammar recognition problem, given a grammar G and a string s of length n, the task is to decide whether s can be obtained from G. Rajasekaran and Yooseph’s parser (JCSS’98) solves this problem in time O(n^2w), where w < 2.373 is the matrix multiplication exponent. The best algorithms avoiding fast matrix multiplication take time O(n^6). The first evidence for hardness was given by Satta (J. Comp. Linguist.’94): For a more general parsing problem, any algorithm that avoids fast matrix multiplication and is significantly faster than O(|G|·n^6) in the case of |G| = Theta(n^12) would imply a breakthrough for Boolean matrix multiplication. Following an approach by Abboud et al. (FOCS’15) for context-free grammar recognition, in this paper we resolve many of the disadvantages of the previous lower bound. We show that, even on constant-size grammars, any improvement on Rajasekaran and Yooseph’s parser would imply a breakthrough for the k-Clique problem. This establishes tree-adjoining grammar parsing as a practically relevant problem with the unusual running time of n^2w , up to lower order factors.