We consider the 1 | | ∑ w j U j problem, the problem of minimizing the weighted number of tardy jobs on a single machine. This problem is one of the most basic and fundamental problems in scheduling theory, with several different applications both in theory and practice. Using a reduction from the Multicolored Clique problem, we prove that 1 | | ∑ w j U j is W[1]-hard with respect to the number p # of different processing times in the input, as well as with respect to the number w # of different weights in the input. This, along with previous work, provides a complete picture for 1 | | ∑ w j U j from the perspective of parameterized complexity, as well as almost tight complexity bounds for the problem under the Exponential Time Hypothesis (ETH).

This paper focuses on kernelization algorithms for the fundamental Knapsack problem. A kernelization algorithm (or kernel) is a polynomial-time reduction from a problem onto itself, where the output size is bounded by a function of some problem-specific parameter. Such algorithms provide a theoretical model for data reduction and preprocessing and are central in the area of parameterized complexity. In this way, a kernel for Knapsack for some parameter $k$ reduces any instance of Knapsack to an equivalent instance of size at most $f(k)$ in polynomial time, for some computable function $f(\cdot)$. When $f(k)=k^{O(1)}$ then we call such a reduction a polynomial kernel. Our study focuses on two natural parameters for Knapsack: The number of different item weights $w_{\#}$, and the number of different item profits $p_{\#}$. Our main technical contribution is a proof showing that Knapsack does not admit a polynomial kernel for any of these two parameters under standard complexity-theoretic assumptions. Our proof discovers an elaborate application of the standard kernelization lower bound framework, and develops along the way novel ideas that should be useful for other problems as well. We complement our lower bounds by showing the Knapsack admits a polynomial kernel for the combined parameter $w_{\#}+p_{\#}$.

In this paper we consider the fundamental scheduling problem of minimizing the weighted number of tardy jobs on a single machine. We present a simple pseudo polynomial-time algorithm for this problem that improves upon the classical Lawler and Moore algorithm from the late 60’s under certain scenarios and parameter settings. Our algorithm uses (max,+)-convolutions as its main tool, exploiting recent improved algorithms for computing such convolutions, and obtains several different running times depending on the specific improvement used. We also provide a related lower bound for the problem under a variant of the well-known Strong Exponential Time Hypothesis (SETH). History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms – Discrete. Funding: This work was supported by the Israel Science Foundation [Grant 1070/20].

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.

Given N instances (X1,t1),…,(XN,tN) of Subset Sum, the AND Subset Sum problem asks to determine whether all of these instances are yes-instances; that is, whether each set of integers Xi has a subset that sums up to the target integer ti. We prove that this problem cannot be solved in time O˜((N⋅tmax)1−ε), for tmax=maxi⁡ti and any ε>0, assuming the ∀∃ Strong Exponential Time Hypothesis (∀∃-SETH). We then use this result to exclude O˜(n+pmax⋅n1−ε)-time algorithms for several scheduling problems on n jobs with maximum processing time pmax, assuming ∀∃-SETH. These include classical problems such as 1||∑wjUj, the problem of minimizing the total weight of tardy jobs on a single machine, and P2||∑Uj, the problem of minimizing the number of tardy jobs on two identical parallel machines.

Subset Sumand k -SAT are two of the most extensively studied problems in computer science, and conjectures about their hardness are among the cornerstones of fine-grained complexity. An important open problem in this area is to base the hardness of one of these problems on the other. Our main result is a tight reduction from k -SAT to Subset Sum on dense instances, proving that Bellman’s 1962 pseudo-polynomial O * ( T )-time algorithm for Subset Sum on n numbers and target T cannot be improved to time T 1-ε · 2 o(n) for any ε > 0, unless the Strong Exponential Time Hypothesis (SETH) fails. As a corollary, we prove a “Direct-OR” theorem for Subset Sum under SETH, offering a new tool for proving conditional lower bounds: It is now possible to assume that deciding whether one out of N given instances of Subset Sum is a YES instance requires time ( N T ) 1-o(1) . As an application of this corollary, we prove a tight SETH-based lower bound for the classical Bicriteria s,t -Path problem, which is extensively studied in Operations Research. We separate its complexity from that of Subset Sum: On graphs with m edges and edge lengths bounded by L , we show that the O ( Lm ) pseudo-polynomial time algorithm by Joksch from 1966 cannot be improved to Õ( L + m ), in contrast to a recent improvement for Subset Sum (Bringmann, SODA 2017).

We introduce a natural but seemingly yet unstudied generalization of the problem of scheduling jobs on a single machine so as to minimize the number of tardy jobs. Our generalization lies in simultaneously considering several instances of the problem at once. In particular, we have n clients over a period of m days, where each client has a single job with its own processing time and deadline per day. Our goal is to provide a schedule for each of the m days, so that each client is guaranteed to have their job meet its deadline in at least k

We present a data structure that in a dynamic graph of treedepth at most d, which is modified over time by edge insertions and deletions, maintains an optimum-height elimination forest. The data structure achieves worst-case update time , which matches the best known parameter dependency in the running time of a static fpt algorithm for computing the treedepth of a graph. This improves a result of Dvořák et al. [ESA 2014], who for the same problem achieved update time f(d) for some non-elementary (i.e. tower-exponential) function f. As a by-product, we improve known upper bounds on the sizes of minimal obstructions for having treedepth d from doubly-exponential in d to dO(d). As applications, we design new fully dynamic parameterized data structures for detecting long paths and cycles in general graphs. More precisely, for a fixed parameter k and a dynamic graph G, modified over time by edge insertions and deletions, our data structures maintain answers to the following queries: Does G contain a simple path on k vertices? Does G contain a simple cycle on at least k vertices? In the first case, the data structure achieves amortized update time . In the second case, the amortized update time is . In both cases we assume access to a dictionary on the edges of G.

In this paper we consider the $p$-Norm Hamming Centroid problem which asks to determine whether some given binary strings have a centroid with a bound on the $p$-norm of its Hamming distances to the strings. Specifically, given a set of strings $S$ and a real $k$, we consider the problem of determining whether there exists a string $s^*$ with $\big(\sum_{s \in S}d^p(s^*,s)\big)^{1/p} \leq k$, where $d(,)$ denotes the Hamming distance metric. This problem has important applications in data clustering, and is a generalization of the well-known polynomial-time solvable \textsc{Consensus String} $(p=1)$ problem, as well as the NP-hard \textsc{Closest String} $(p=\infty)$ problem. Our main result shows that the problem is NP-hard for all fixed rational $p > 1$, closing the gap for all rational values of $p$ between $1$ and $\infty$. Under standard complexity assumptions the reduction also implies that the problem has no $2^{o(n+m)}$-time or $2^{o(k^{\frac{p}{(p+1)}})}$-time algorithm, where $m$ denotes the number of input strings and $n$ denotes the length of each string, for any fixed $p > 1$. Both running time lower bounds are tight. In particular, we provide a $2^{k^{\frac{p}{(p+1)}+\varepsilon}}$-time algorithm for each fixed $\varepsilon > 0$. In the last part of the paper, we complement our hardness result by presenting a fixed-parameter algorithm and a factor-$2$ approximation algorithm for the problem.

Subset Sum and k-SAT are two of the most extensively studied problems in computer science, and conjectures about their hardness are among the cornerstones of fine-grained complexity. An important open problem in this area is to base the hardness of one of these problems on the other. Our main result is a tight reduction from k-SAT to Subset Sum on dense instances, proving that Bellman's 1962 pseudo-polynomial O*(T)-time algorithm for Subset Sum on n numbers and target T cannot be improved to time T1–ε · 2o(n) for any ε > 0, unless the Strong Exponential Time Hypothesis (SETH) fails. As a corollary, we prove a “Direct-OR” theorem for Subset Sum under SETH, offering a new tool for proving conditional lower bounds: It is now possible to assume that deciding whether one out of N given instances of Subset Sum is a YES instance requires time (NT)1–o(1). As an application of this corollary, we prove a tight SETH-based lower bound for the classical Bicriteria s, t-PATH problem, which is extensively studied in Operations Research. We separate its complexity from that of Subset Sum: On graphs with m edges and edge lengths bounded by L, we show that the O(Lm) pseudo-polynomial time algorithm by Joksch from 1966 cannot be improved to Õ(L + m), in contrast to a recent improvement for Subset Sum (Bringmann, SODA 2017).

We algorithmize the structural characterization for claw-free graphs by Chudnovsky and Seymour. Building on this result, we show that D ominating S et on claw-free graphs is (i) fixed-parameter tractable and (ii) even possesses a polynomial kernel. To complement these results, we establish that D ominating S et is unlikely to be fixed-parameter tractable on the slightly larger class of graphs that exclude K 1,4 as an induced subgraph ( K 1,4 -free graphs). We show that our algorithmization can also be used to show that the related C onnected D ominating S et problem is fixed-parameter tractable on claw-free graphs. To complement that result, we show that C onnected D ominating S et is unlikely to have a polynomial kernel on claw-free graphs and is unlikely to be fixed-parameter tractable on K 1,4 -free graphs. Combined, our results provide a dichotomy for D ominating S et and C onnected D ominating S et on K 1,ℓ -free graphs and show that the problem is fixed-parameter tractable if and only if ℓ ≤ 3.

The classic Stable Roommates problem (the non-bipartite generalization of the well-known Stable Marriage problem) asks whether there is a stable matching for a given set of agents, i.e. a partitioning of the agents into disjoint pairs such that no two agents induce a blocking pair. Herein, each agent has a preference list denoting who it prefers to have as a partner, and two agents are blocking if they prefer to be with each other rather than with their assigned partners. Since stable matchings may not be unique, we study an NP-hard optimization variant of Stable Roommates, called Egal Stable Roommates, which seeks to find a stable matching with a minimum egalitarian cost gamma, i.e. the sum of the dissatisfaction of the agents is minimum. The dissatisfaction of an agent is the number of agents that this agent prefers over its partner if it is matched; otherwise it is the length of its preference list. We also study almost stable matchings, called Min-Block-Pair Stable Roommates, which seeks to find a matching with a minimum number beta of blocking pairs. Our main result is that Egal Stable Roommates parameterized by gamma is fixed-parameter tractable, while Min-Block-Pair Stable Roommates parameterized by beta is W[1]-hard, even if the length of each preference list is at most five.

The composition technique is a popular method for excluding polynomial-size problem kernels for NP-hard parameterized problems. We present a new technique exploiting triangle-based fractal structures for extending the range of applicability of compositions. Our technique makes it possible to prove new no-polynomial-kernel results for a number of problems dealing with length-bounded cuts. In particular, answering an open question of Golovach and Thilikos [ Discrete Optim., 8 (2011), pp. 77--86], we show that, unless ${NP}\subseteq {{coNP}}/{{poly}}$, the NP-hard Length-Bounded Edge-Cut (LBEC) problem (delete at most $k$ edges such that the resulting graph has no $s$-$t$ path of length shorter than $\ell$) parameterized by the combination of $k$ and $\ell$ has no polynomial-size problem kernel. Our framework applies to planar as well as directed variants of the basic problems and also applies to both edge and vertex-deletion problems. Along the way, we show that LBEC remains NP-hard on planar graphs, a result which we believe is interesting in its own right.

In this paper, we study the Connected H-hitting Set and Dominating Set problems from the perspective of approximate kernelization, a framework recently introduced by Lokshtanov et al. [STOC 2017]. For the Connected H-hitting set problem, we obtain an \alpha-approximate kernel for every \alpha>1 and complement it with a lower bound for the natural weighted version. We then perform a refined analysis of the tradeoff between the approximation factor and kernel size for the Dominating Set problem on d-degenerate graphs and provide an interpolation of approximate kernels between the known d^2-approximate kernel of constant size and 1-approximate kernel of size k^{O(d^2)}.

Kernelization is a strong and widely applied technique in parameterized complexity. In a nutshell, a kernelization algorithm for a parameterized problem transforms in polynomial time a given instance of the problem into an equivalent instance whose size depends solely on the parameter. Recent years have seen major advances in the study of both upper and lower bound techniques for kernelization, and by now this area has become one of the major research threads in parameterized complexity. In this article, we consider kernelization for problems on d -degenerate graphs, that is, graphs such that any subgraph contains a vertex of degree at most d . This graph class generalizes many classes of graphs for which effective kernelization is known to exist, for example, planar graphs, H -minor free graphs, and H -topological-minor free graphs. We show that for several natural problems on d -degenerate graphs the best-known kernelization upper bounds are essentially tight. In particular, using intricate constructions of weak compositions, we prove that unless coNP ⊆ NP/poly: • D ominating S et has no kernels of size O ( k ( d −1)( d −3)−ε ) for any ε > 0. The current best upper bound is O ( k (d+1) 2 ). • I ndependent D ominating S et has no kernels of size O ( k d −4−ε ) for any ε > 0. The current best upper bound is O ( k d +1 ). • I nduced M atching has no kernels of size O ( k d −3−ε ) for any ε > 0. The current best upper bound is O ( k d ). To the best of our knowledge, D ominating S et is the the first problem where a lower bound with superlinear dependence on d (in the exponent) can be proved. In the last section of the article, we also give simple kernels for C onnected V ertex C over and C apacitated V ertex C over of size O ( k d ) and O ( k d +1 ), respectively. We show that the latter problem has no kernels of size O ( k d −ε ) unless coNP ⊆ NP/poly by a simple reduction from d -E xact S et C over (the same lower bound for C onnected V ertex C over on d -degenerate graphs is already known).

Bodlaender et al.'s [Bodlaender/Jansen/Kratsch,2014] cross-composition technique is a popular method for excluding polynomial-size problem kernels for NP-hard parameterized problems. We present a new technique exploiting triangle-based fractal structures for extending the range of applicability of cross-compositions. Our technique makes it possible to prove new no-polynomial-kernel results for a number of problems dealing with length-bounded cuts. Roughly speaking, our new technique combines the advantages of serial and parallel composition. In particular, answering an open question of Golovach and Thilikos [Golovach/Thilikos,2011], we show that, unless NP subseteq coNP/poly, the NP-hard Length-Bounded Edge-Cut problem (delete at most k edges such that the resulting graph has no s-t path of length shorter than l) parameterized by the combination of k and l has no polynomial-size problem kernel. Our framework applies to planar as well as directed variants of the basic problems and also applies to both edge and vertex deletion problems.

We consider the following graph cut problem called Critical Node Cut (CNC): Given a graph G on n vertices, and two positive integers k and x, determine whether G has a set of k vertices whose removal leaves G with at most x connected pairs of vertices. We analyze this problem in the framework of parameterized complexity. That is, we are interested in whether or not this problem is solvable in f(kappa) * n^{O(1)} time (i.e., whether or not it is fixed-parameter tractable), for various natural parameters kappa. We consider four such parameters: - The size k of the required cut. - The upper bound x on the number of remaining connected pairs. - The lower bound y on the number of connected pairs to be removed. - The treewidth w of G. We determine whether or not CNC is fixed-parameter tractable for each of these parameters. We determine this also for all possible aggregations of these four parameters, apart from w+k. Moreover, we also determine whether or not CNC admits a polynomial kernel for all these parameterizations. That is, whether or not there is an algorithm that reduces each instance of CNC in polynomial time to an equivalent instance of size kappa^{O(1)}, where kappa is the given parameter.

We study a scheduling problem where two agents (each equipped with a private set of jobs) compete to perform their respective jobs on a common single machine. Each agent wants to keep the weighted sum of completion times of his jobs below a given (agent-dependent) bound. This problem is known to be NP-hard, even for quite restrictive settings of the problem parameters. We consider parameterized versions of the problem where one of the agents has a small number of jobs (and where this small number constitutes the parameter). The problem becomes much more tangible in this case, and we present three positive algorithmic results for it. Our study is complemented by showing that the general problem is NP-complete even when one agent only has a single job.

We consider the Steiner Multicut problem, which asks, given an undirected graph G, a collection T = \{T_{1},...,T_{t}}, T_i \subseteq V(G), of terminal sets of size at most p, and an integer k, whether there is a set S of at most k edges or nodes such that of each set T_{i} at least one pair of terminals is in different connected components of G \ S. This problem generalizes several well-studied graph cut problems, in particular the Multicut problem, which corresponds to the case p = 2. The Multicut problem was recently shown to be fixed-parameter tractable for parameter k [Marx and Razgon, Bousquet et al., STOC 2011]. The question whether this result generalizes to Steiner Multicut motivates the present work. We answer the question that motivated this work, and in fact provide a dichotomy of the parameterized complexity of Steiner Multicut on general graphs. That is, for any combination of k, t, p, and the treewidth tw(G) as constant, parameter, or unbounded, and for all versions of the problem (edge deletion and node deletion with and without deletable terminals), we prove either that the problem is fixed-parameter tractable or that the problem is hard (W[1]-hard or even (para-)NP-complete). Among the many results in the paper, we highlight that: - The edge deletion version of Steiner Multicut is fixed-parameter tractable for parameter k+t on general graphs (but has no polynomial kernel, even on trees). - In contrast, both node deletion versions of Steiner Multicut are W[1]-hard for the parameter k+t on general graphs. - All versions of Steiner Multicut are W[1]-hard for the parameter k, even when p=3 and the graph is a tree plus one node. Since we allow k, t, p, and tw(G) to be any constants, our characterization includes a dichotomy for Steiner Multicut on trees (for tw(G) = 1) as well as a polynomial time versus NP-hardness dichotomy (by restricting k,t,p,tw(G) to constant or unbounded).

In this paper we use the notion of weak compositions to obtain polynomial kernelization lower-bounds for several natural parameterized problems. Let d ≥ 2 be some constant and let L1, L2 ⊆ {0, 1}* × ℕ be two parameterized problems where the unparameterized version of L1 is NP-hard. Assuming coNP ⊆ NP/poly, our framework essentially states that composing t L1-instances each with parameter k, to an L2-instance with parameter k′ ≤ t1/dkO(1), implies that L2 does not have a kernel of size O(kd − ε) for any ε > 0. We show two examples of weak composition and derive polynomial kernelization lower bounds for d-Bipartite Regular Perfect Code and d-Dimensional Matching, parameterized by the solution size k. By reduction, using linear parameter transformations, we then derive the following lower-bounds for kernel sizes when the parameter is the solution size k (assuming coNP ⊆ NP/poly): d-Set Packing, d-Set Cover, d-Exact Set Cover, Hitting Set with d-Bounded Occurrences, and Exact Hitting Set with d-Bounded Occurrences have no kernels of size O(kd–3–ε) for any ε > 0. Kd Packing and Induced K1,d Packing have no kernels of size O(kd–4–ε) for any ε > 0. d-Red-Blue Dominating Set and d-Steiner Tree have no kernels of sizes O(kd–3–ε) and O(kd−4−ε), respectively, for any ε > 0. Our results give a negative answer to an open question raised by Dom, Lokshtanov, and Saurabh [ICALP2009] regarding the existence of uniform polynomial kernels for the problems above. All our lower bounds transfer automatically to compression lower bounds, a notion defined by Harnik and Naor [SICOMP2010] to study the compressibility of NP instances with cryptographic applications. We believe weak composition can be used to obtain polynomial kernelization lower bounds for other interesting parameterized problems. In the last part of the paper we strengthen previously known super-polynomial kernelization lower bounds to super-quasi-polynomial lower bounds, by showing that quasi-polynomial kernels for compositional NP-hard parameterized problems implies the collapse of the exponential hierarchy. These bounds hold even the kernelization algorithms are allowed to run in quasi-polynomial time.

We examine the complexity of constraint satisfaction problems that consist of a set of AllDiff constraints. Such CSPs naturally model a wide range of real-world and combinatorial problems, like scheduling, frequency allocations and graph coloring problems. As this problem is known to be NP-complete, we investigate under which further assumptions it becomes tractable. We observe that a crucial property seems to be the convexity of the variable domains and constraints. Our main contribution is an extensive study of the complexity of Multiple AllDiff CSPs for a set of natural parameters, like maximum domain size and maximum size of the constraint scopes. We show that, depending on the parameter, convexity can make the problem tractable while it is provably intractable in general

The haplotype inference problem (HIP) asks to find a set of haplotypes which resolve a given set of genotypes. This problem is important in practical fields such as the investigation of diseases or other types of genetic mutations. In order to find the haplotypes which are as close as possible to the real set of haplotypes that comprise the genotypes, two models have been suggested which are by now well-studied: The perfect phylogeny model and the pure parsimony model. All known algorithms up till now for haplotype inference may find haplotypes that are not necessarily plausible, i.e., very rare haplotypes or haplotypes that were never observed in the population. In order to overcome this disadvantage, we study in this paper, a new constrained version of HIP under the above-mentioned models. In this new version, a pool of plausible haplotypes H is given together with the set of genotypes G, and the goal is to find a subset H ⊆ H that resolves G. For constrained perfect phlogeny haplotyping (CPPH), we provide initial insights and polynomial-time algorithms for some restricted cases of the problem. For constrained parsimony haplotyping (CPH), we show that the problem is fixed parameter tractable when parameterized by the size of the solution set of haplotypes.

The Nemhauser–Trotter theorem provides an algorithm which is frequently used as a subroutine in approximation algorithms for the classical Vertex Cover problem. In this paper we present an extension of this theorem so it fits a more general variant of Vertex Cover, namely, the Generalized Vertex Cover problem, where edges are allowed not to be covered at a certain predetermined penalty. We show that many applications of the original Nemhauser–Trotter theorem can be applied using our extension to Generalized Vertex Cover. These applications include a $(2-2/d)$-approximation algorithm for graphs of bounded degree d, a polynomial-time approximation scheme (PTAS) for planar graphs, a $(2-\lg\lg n/2\lg n)$-approximation algorithm for general graphs, and a $2k$ kernel for the parameterized Generalized Vertex Cover problem.

Multiple-interval graphs are a natural generalization of interval graphs where each vertex may have more then one interval associated with it. We initiate the study of optimization problems in multiple-interval graphs by considering three classical problems: Minimum Vertex Cover, Minimum Dominating Set, and Maximum Clique. We describe applications for each one of these problems, and then proceed to discuss approximation algorithms for them. Our results can be summarized as follows: Let t be the number of intervals associated with each vertex in a given multiple-interval graph. For Minimum Vertex Cover, we give a (2−1/ t )-approximation algorithm which also works when a t -interval representation of our given graph is absent. Following this, we give a t 2 -approximation algorithm for Minimum Dominating Set which adapts well to more general variants of the problem. We then proceed to prove that Maximum Clique is NP -hard already for 3-interval graphs, and provide a ( t 2 − t +1)/2-approximation algorithm for general values of t ≥ 2, using bounds proven for the so-called transversal number of t -interval families.

The Target Set Selection problem proposed by Kempe, Kleinberg, and Tardos, gives a nice clean combinatorial formulation for many problems arising in economy, sociology, and medicine. Its input is a graph with vertex thresholds, the social network, and the goal is to find a subset of vertices, the target set, that "activates" a prespecified number of vertices in the graph. Activation of a vertex is defined via a so-called activation process as follows: Initially, all vertices in the target set become active. Then at each step i of the process, each vertex gets activated if the number of its active neighbors at iteration i -- 1 exceeds its threshold. The activation process is "monotone" in the sense that once a vertex is activated, it remains active for the entire process.

The edit distance problem is a classical fundamental problem in computer science in general, and in combinatorial pattern matching in particular. The standard dynamic-programming solution for this problem computes the edit-distance between a pair of strings of total length $O(N)$ in $O(N^2)$ time. To this date, this quadratic upper-bound has never been substantially improved for general strings. However, there are known techniques for breaking this bound in case the strings are known to compress well under a particular compression scheme. The basic idea is to first compress the strings, and then to compute the edit distance between the compressed strings. As it turns out, practically all known $o(N^2)$ edit-distance algorithms work, in some sense, under the same paradigm described above. It is therefore natural to ask whether there is a single edit-distance algorithm that works for strings which are compressed under any compression scheme. A rephrasing of this question is to ask whether a single algorithm can exploit the compressibility properties of strings under any compression method, even if each string is compressed using a different compression. In this paper we set out to answer this question by using \emph{straight-line programs}. These provide a generic platform for representing many popular compression schemes including the LZ-family, Run-Length Encoding, Byte-Pair Encoding, and dictionary methods. For two strings of total length $N$ having straight-line program representations of total size $n$, we present an algorithm running in $O(n^{1.4}N^{1.2})$ time for computing the edit-distance of these two strings under any rational scoring function, and an $O(n^{1.34}N^{1.34})$-time algorithm for arbitrary scoring functions. This improves on a recent algorithm of Tiskin that runs in $O(nN^{1.5})$ time, and works only for rational scoring functions.