The dual of a planar graph G is a planar graph G* that has a vertex for each face of G and an edge for each pair of adjacent faces of G. The profound relationship between a planar graph and its dual has been the algorithmic basis for solving numerous (centralized) classical problems on planar graphs involving distances, flows, and cuts. In the distributed setting however, the only use of planar duality is for finding a recursive decomposition of G [DISC 2017, STOC 2019].

Dynamic Time Warping (DTW) distance is the optimal cost of matching two strings when extending runs of letters is for free. Therefore, it is natural to measure the time complexity of DTW in terms of the number of runs n (rather than the string lengths N). In this paper, we give an Õ(n²) time algorithm for computing the DTW distance. This matches (up to log factors) the known (conditional) lower bound, and should be compared with the previous fastest O(n³) time exact algorithm and the Õ(n²) time approximation algorithm. Our method also immediately implies an Õ(nk) time algorithm when the distance is bounded by k. This should be compared with the previous fastest O(n²k) and O(Nk) time exact algorithms and the Õ(nk) time approximation algorithm.

Abstract We give a randomized algorithm that finds a minimum cut in an undirected weighted m-edge n-vertex graph G with high probability in $$O(m \log ^2 n)$$ O ( m log 2 n ) time. This is the first improvement to Karger’s celebrated $$O(m \log ^3 n)$$ O ( m log 3 n ) time algorithm from 1996. Our main technical contribution is a deterministic $$O(m \log n)$$ O ( m log n ) time algorithm that, given a spanning tree T of G, finds a minimum cut of G that 2-respects (cuts two edges of) T.

The Voronoi diagrams technique was introduced by Cabello to compute the diameter of planar graphs in subquadratic time. We present novel applications of this technique in static, fault-tolerant, and partially-dynamic undirected unweighted planar graphs, as well as some new limitations. 1. In the static case, we give $n^{3+o(1)}/D^2$ and $\tilde{O}(n\cdot D^2)$ time algorithms for computing the diameter of a planar graph $G$ with diameter $D$. These are faster than the state of the art $\tilde{O}(n^{5/3})$ when $Dn^{2/3}$. 2. In the fault-tolerant setting, we give an $n^{7/3+o(1)}$ time algorithm for computing the diameter of $G\setminus \{e\}$ for every edge $e$ in $G$ the replacement diameter problem. Compared to the naive $\tilde{O}(n^{8/3})$ time algorithm that runs the static algorithm for every edge. 3. In the incremental setting, where we wish to maintain the diameter while while adding edges, we present an algorithm with total running time $n^{7/3+o(1)}$. Compared to the naive $\tilde{O}(n^{8/3})$ time algorithm that runs the static algorithm after every update. 4. We give a lower bound (conditioned on the SETH) ruling out an amortized $O(n^{1-\varepsilon})$ update time for maintaining the diameter in *weighted* planar graph. The lower bound holds even for incremental or decremental updates. Our upper bounds are obtained by novel uses and manipulations of Voronoi diagrams. These include maintaining the Voronoi diagram when edges of the graph are deleted, allowing the sites of the Voronoi diagram to lie on a BFS tree level (rather than on boundaries of $r$-division), and a new reduction from incremental diameter to incremental distance oracles that could be of interest beyond planar graphs. Our lower bound is the first lower bound for a dynamic planar graph problem that is conditioned on the SETH.

We consider the problem of preprocessing a weighted directed planar graph in order to quickly answer exact distance queries. The main tension in this problem is between space S and query time Q , and since the mid-1990s all results had polynomial time-space tradeoffs, e.g., Q = ~ Θ( n/√ S ) or Q = ~Θ( n 5/2 /S 3/2 ). In this article we show that there is no polynomial tradeoff between time and space and that it is possible to simultaneously achieve almost optimal space n 1+ o (1) and almost optimal query time n o (1) . More precisely, we achieve the following space-time tradeoffs: n 1+ o (1) space and log 2+ o (1) n query time, n log 2+ o (1) n space and n o (1) query time, n 4/3+ o (1) space and log 1+ o (1) n query time. We reduce a distance query to a variety of point location problems in additively weighted Voronoi diagrams and develop new algorithms for the point location problem itself using several partially persistent dynamic tree data structures.

Given two strings S and P, the Episode Matching problem is to find the shortest substring of S that contains P as a subsequence. The best known upper bound for this problem is Õ(nm) by Das et al. (1997), where n,m are the lengths of S and P, respectively. Although the problem is well studied and has many applications in data mining, this bound has never been improved. In this paper we show why this is the case by proving that no O((nm)^{1-ε}) algorithm (even for binary strings) exists, unless the Strong Exponential Time Hypothesis (SETH) is false. We then consider the indexing version of the problem, where S is preprocessed into a data structure for answering episode matching queries P. We show that for any τ, there is a data structure using O(n+(n/(τ)) ^k) space that answers episode matching queries for any P of length k in O(k⋅ τ ⋅ log log n) time. We complement this upper bound with an almost matching lower bound, showing that any data structure that answers episode matching queries for patterns of length k in time O(n^δ), must use Ω(n^{k-kδ-o(1)}) space, unless the Strong k-Set Disjointness Conjecture is false. Finally, for the special case of k = 2, we present a faster construction of the data structure using fast min-plus multiplication of bounded integer matrices.

We consider the problem of preprocessing two strings S and T, of lengths m and n, respectively, in order to be able to efficiently answer the following queries: Given positions i,j in S and positions a,b in T, return the optimal alignment score of S[i..j] and T[a..b]. Let N = mn. We present an oracle with preprocessing time N^{1+o(1)} and space N^{1+o(1)} that answers queries in log^{2+o(1)}N time. In other words, we show that we can efficiently query for the alignment score of every pair of substrings after preprocessing the input for almost the same time it takes to compute just the alignment of S and T. Our oracle uses ideas from our distance oracle for planar graphs [STOC 2019] and exploits the special structure of the alignment graph. Conditioned on popular hardness conjectures, this result is optimal up to subpolynomial factors. Our results apply to both edit distance and longest common subsequence (LCS). The best previously known oracle with construction time and size 𝒪(N) has slow Ω(√N) query time [Sakai, TCS 2019], and the one with size N^{1+o(1)} and query time log^{2+o(1)}N (using a planar graph distance oracle) has slow Ω(N^{3/2}) construction time [Long & Pettie, SODA 2021]. We improve both approaches by roughly a √ N factor.

Given an edge-weighted directed graph G, the Negative-k-Cycle problem asks whether G contains a negative-weight cycle with at most k edges. For k = 3 the problem is known as the NegativeTriangle problem and is equivalent to all-pairs shortest paths (and to min-plus matrix multiplication) and solvable in O(n3) time. In this paper, we consider the case of directed planar graphs. We show that the Negative-k-Cycle problem can be solved in min{O(nk2 log n), O(n2)} time. Assuming the min-plus convolution conjecture, we then show, for k > n1/3 that there is no algorithm polynomially faster than , and for k ≤ n1/3 that our O(nk2 log n) upper bound is essentially tight. The latter gives the first non-trivial tight bounds for a planar graph problem in P. Our lower bounds are obtained by introducing a natural problem on matrices that generalizes both min-plus matrix multiplication and min-plus convolution, and whose complexity lies between the complexities of these two problems.

We present a compressed representation of tries based on top tree compression [ICALP 2013] that works on a standard, comparison-based, pointer machine model of computation and supports efficient prefix search queries. Namely, we show how to preprocess a set of strings of total length n over an alphabet of size $$\sigma$$ into a compressed data structure of worst-case optimal size $$O(n/\log _\sigma n)$$ that given a pattern string P of length m determines if P is a prefix of one of the strings in time $$O(\min (m\log \sigma ,m + \log n))$$ . We show that this query time is in fact optimal regardless of the size of the data structure. Existing solutions either use $$\Omega (n)$$ space or rely on word RAM techniques, such as tabulation, hashing, address arithmetic, or word-level parallelism, and hence do not work on a pointer machine. Our result is the first solution on a pointer machine that achieves worst-case o(n) space. Along the way, we develop several interesting data structures that work on a pointer machine and are of independent interest. These include an optimal data structures for random access to a grammar-compressed string and an optimal data structure for a variant of the level ancestor problem.

We present an explicit and efficient construction of additively weighted Voronoi diagrams on planar graphs. Let $G$ be a planar graph with $n$ vertices and $b$ sites that lie on a constant number of faces. We show how to preprocess $G$ in $\tilde O(nb^2)$ time so that one can compute any additively weighted Voronoi diagram for these sites in $\tilde O(b)$ time. We use this construction to compute the diameter of a directed planar graph with real arc lengths in $\tilde{O}(n^{5/3})$ time. This improves the recent breakthrough result of Cabello [ SODA 2017, SIAM, Philadelphia, 2017, pp. 2143--2152], both by improving the running time (from $\tilde{O}(n^{11/6})$), and by providing a deterministic algorithm. It is in fact the first truly subquadratic deterministic algorithm for this problem. Our use of Voronoi diagrams to compute the diameter follows that of Cabello, but he used abstract Voronoi diagrams, which makes his diameter algorithm more involved, more expensive, and randomized. As in Cabello's work, our algorithm can compute, for every vertex $v$, both the farthest vertex from $v$ (i.e., the eccentricity of $v$), and the sum of distances from $v$ to all other vertices. Hence, our algorithm can also compute the radius, median, and Wiener index (sum of all pairwise distances) of a planar graph within the same time bounds. Our construction of Voronoi diagrams for planar graphs is of independent interest.

We consider the parity variants of basic problems studied in fine-grained complexity. We show that finding the exact solution is just as hard as finding its parity (i.e. if the solution is even or odd) for a large number of classical problems, including All-Pairs Shortest Paths (APSP), Diameter, Radius, Median, Second Shortest Path, Maximum Consecutive Subsums, Min-Plus Convolution, and $0/1$-Knapsack. A direct reduction from a problem to its parity version is often difficult to design. Instead, we revisit the existing hardness reductions and tailor them in a problem-specific way to the parity version. Nearly all reductions from APSP in the literature proceed via the (subcubic-equivalent but simpler) Negative Weight Triangle (NWT) problem. Our new modified reductions also start from NWT or a non-standard parity variant of it. We are not able to establish a subcubic-equivalence with the more natural parity counting variant of NWT, where we ask if the number of negative triangles is even or odd. Perhaps surprisingly, we justify this by designing a reduction from the seemingly-harder Zero Weight Triangle problem, showing that parity is (conditionally) strictly harder than decision for NWT.

We give a randomized algorithm that finds a minimum cut in an undirected weighted $m$-edge $n$-vertex graph $G$ with high probability in $O(m \log^2 n)$ time. This is the first improvement to Karger's celebrated $O(m \log^3 n)$ time algorithm from 1996. Our main technical contribution is a deterministic $O(m \log n)$ time algorithm that, given a spanning tree $T$ of $G$, finds a minimum cut of $G$ that 2-respects (cuts two edges of) $T$.

The edit distance between two rooted ordered trees with n nodes labeled from an alphabet Ʃ is the minimum cost of transforming one tree into the other by a sequence of elementary operations consisting of deleting and relabeling existing nodes, as well as inserting new nodes. Tree edit distance is a well-known generalization of string edit distance. The fastest known algorithm for tree edit distance runs in cubic O ( n 3 ) time and is based on a similar dynamic programming solution as string edit distance. In this article, we show that a truly subcubic O ( n 3-ε ) time algorithm for tree edit distance is unlikely: For |Ʃ| = Ω ( n ), a truly subcubic algorithm for tree edit distance implies a truly subcubic algorithm for the all pairs shortest paths problem. For |Ʃ| = O (1), a truly subcubic algorithm for tree edit distance implies an O ( n k-ε ) algorithm for finding a maximum weight k -clique. Thus, while in terms of upper bounds string edit distance and tree edit distance are highly related, in terms of lower bounds string edit distance exhibits the hardness of the strong exponential time hypothesis (Backurs, Indyk STOC’15) whereas tree edit distance exhibits the hardness of all pairs shortest paths. Our result provides a matching conditional lower bound for one of the last remaining classic dynamic programming problems.

We present an optimal data structure for submatrix maximum queries in n × n Monge matrices. Our result is a two-way reduction showing that the problem is equivalent to the classical predecessor problem in a universe of polynomial size. This gives a data structure of O ( n ) space that answers submatrix maximum queries in O (log log n ) time, as well as a matching lower bound, showing that O (log log n ) query-time is optimal for any data structure of size O ( n polylog( n )). Our result settles the problem, improving on the O (log 2 n ) query time in SODA’12, and on the O (log n ) query-time in ICALP’14. In addition, we show that partial Monge matrices can be handled in the same bounds as full Monge matrices. In both previous results, partial Monge matrices incurred additional inverse-Ackermann factors.

We present new tradeoffs between space and query-time for exact distance oracles in directed weighted planar graphs. These tradeoffs are almost optimal in the sense that they are within polylogarithmic, subpolynomial or arbitrarily small polynomial factors from the naïve linear space, constant query-time lower bound. These tradeoffs include: (i) an oracle with space O(n1+є) and query-time Õ(1) for any constant є>0, (ii) an oracle with space Õ(n) and query-time O(nє) for any constant є>0, and (iii) an oracle with space n1+o(1) and query-time no(1).

Given a graph G and a set of terminals T, a distance emulator of G is another graph H (not necessarily a subgraph of G) containing T, such that all the pairwise distances in G between vertices of T are preserved in H. An important open question is to find the smallest possible distance emulator. We prove that, given any subset of k terminals in an n-vertex undirected unweighted planar graph, we can construct in O~(n) time a distance emulator of size O~(min(k^2,sqrt{k * n})). This is optimal up to logarithmic factors. The existence of such distance emulator provides a straightforward framework to solve distance-related problems on planar graphs: Replace the input graph with the distance emulator, and apply whatever algorithm available to the resulting emulator. In particular, our result implies that, on any unweighted undirected planar graph, one can compute all-pairs shortest path distances among k terminals in O~(n) time when k=O(n^{1/3}).

A consensus tree is a phylogenetic tree that captures the similarity between a set of conflicting phylogenetic trees. The problem of computing a consensus tree is a major step in phylogenetic tree reconstruction. It also finds applications in predicting a species tree from a set of gene trees. This paper focuses on two of the most well-known and widely used oconsensus tree methods: the greedy consensus tree and the frequency difference consensus tree. Given $k$ conflicting trees each with $n$ leaves, the previous fastest algorithms for these problems were $O(k n^2)$ for the greedy consensus tree [J. ACM 2016] and $\tilde O(\min \{ k n^2, k^2n\})$ for the frequency difference consensus tree [ACM TCBB 2016]. We improve these running times to $\tilde O(k n^{1.5})$ and $\tilde O(k n)$ respectively.

Given a set W = {w_1,..., w_n} of non-negative integer weights and an integer C, the #Knapsack problem asks to count the number of distinct subsets of W whose total weight is at most C. In the more general integer version of the problem, the subsets are multisets. That is, we are also given a set {u_1,..., u_n} and we are allowed to take up to u_i items of weight w_i. We present a deterministic FPTAS for #Knapsack running in O(n^{2.5}epsilon^{-1.5}log(n epsilon^{-1})log (n epsilon)) time. The previous best deterministic algorithm [FOCS 2011] runs in O(n^3 epsilon^{-1} log(n epsilon^{-1})) time (see also [ESA 2014] for a logarithmic factor improvement). The previous best randomized algorithm [STOC 2003] runs in O(n^{2.5} sqrt{log (n epsilon^{-1})} + epsilon^{-2} n^2) time. Therefore, for the case of constant epsilon, we close the gap between the O~(n^{2.5}) randomized algorithm and the O~(n^3) deterministic algorithm. For the integer version with U = max_i {u_i}, we present a deterministic FPTAS running in O(n^{2.5}epsilon^{-1.5}log(n epsilon^{-1} log U)log (n epsilon) log^2 U) time. The previous best deterministic algorithm [TCS 2016] runs in O(n^3 epsilon^{-1}log(n epsilon^{-1} log U) log^2 U) time.

The Planar Graph Metric Compression Problem is to compactly encode the distances among k nodes in a planar graph of size n. Two naïve solutions are to store the graph using O(n) bits, or to explicitly store the distance matrix with O(k2 log n) bits. The only lower bounds are from the seminal work of Gavoille, Peleg, Prennes, and Raz [SODA’01], who rule out compressions into a polynomially smaller number of bits, for weighted planar graphs, but leave a large gap for unweighted planar graphs. For example, when , the upper bound is O(n) and their constructions imply an Ω(n3/4) lower bound. This gap is directly related to other major open questions in labeling schemes, dynamic algorithms, and compact routing. Our main result is a new compression of the planar graph metric into bits, which is optimal up to log factors. Our data structure circumvents an Õ(k2) lower bound of Krauthgamer, Nguyen, and Zondiner [SIDMA’14] for compression using minors, and the lower bound of Gavoille et al. for compression of weighted planar graphs. This is an unexpected and decisive proof that weights can make planar graphs inherently more complex. Moreover, we design a new Subset Distance Oracle for planar graphs with space, and Õ(n3/4) query time. Our work carries strong messages to related fields. In particular, the famous O(n1/2) vs. Ω(n1/3) gap for distance labeling schemes in planar graphs cannot be resolved with the current lower bound techniques. On the positive side, we introduce the powerful tool of unit-monge to planar graph algorithms.

The edit distance between two rooted ordered trees with n nodes labeled from an alphabet Σ is the minimum cost of transforming one tree into the other by a sequence of elementary operations consisting of deleting and relabeling existing nodes, as well as inserting new nodes. Tree edit distance is a well known generalization of string edit distance. The fastest known algorithm for tree edit distance runs in cubic O(n3) time and is based on a similar dynamic programming solution as string edit distance. In this paper we show that a truly subcubic O(n3–ε) time algorithm for tree edit distance is unlikely: For |Σ| = Ω(n), a truly subcubic algorithm for tree edit distance implies a truly subcubic algorithm for the all pairs shortest paths problem. For |Σ| = O(1), a truly subcubic algorithm for tree edit distance implies an O(nk–ε) algorithm for finding a maximum weight k-clique. Thus, while in terms of upper bounds string edit distance and tree edit distance are highly related, in terms of lower bounds string edit distance exhibits the hardness of the strong exponential time hypothesis [Backurs, Indyk STOC’15] whereas tree edit distance exhibits the hardness of all pairs shortest paths. Our result provides a matching conditional lower bound for one of the last remaining classic dynamic programming problems.

We present an efficient construction of additively weighted Voronoi diagrams on planar graphs. Let G be a planar graph with n vertices and b sites that lie on a constant number of faces. We show how to preprocess G in Õ(nb2) time1 so that one can compute any additively weighted Voronoi diagram for these sites in Õ(b) time. We use this construction to compute the diameter of a directed planar graph with real arc lengths in Õ(n5/3) time. This improves the recent breakthrough result of Cabello (SODA’17), both by improving the running time (from Õ(n11/6)), and by providing a deterministic algorithm. It is in fact the first truly subquadratic deterministic algorithm for this problem. Our use of Voronoi diagrams to compute the diameter follows that of Cabello, but he used abstract Voronoi diagrams, which makes his diameter algorithm more involved, more expensive, and randomized. As in Cabello's work, our algorithm can also compute the Wiener index of a planar graph (i.e., the sum of all pairwise distances) within the same bound. Our construction of Voronoi diagrams for planar graphs is of independent interest. It has already been used to obtain fast exact distance oracles for planar graphs [Cohen-Addad et al., FOCS’17].

We present an O(n1.5)-space distance oracle for directed planar graphs that answers distance queries in O(log n) time. Our oracle both significantly simplifies and significantly improves the recent oracle of Cohen-Addad, Dahlgaard and Wulff-Nilsen [FOCS 2017], which uses O(n5/3)-space and answers queries in O(log n) time. We achieve this by designing an elegant and efficient point location data structure for Voronoi diagrams on planar graphs. We further show a smooth tradeoff between space and query-time. For any S ∊ [n, n2], we show an oracle of size S that answers queries in Õ(max{1, n1.5/S}) time. This new tradeoff is currently the best (up to polylogarithmic factors) for the entire range of S and improves by polynomial factors over all previously known tradeoffs for the range S ∊ [n, n5/3].

We give an O(n log log n) time algorithm for computing the minimum cut (or equivalently, the shortest cycle) of a weighted directed planar graph. This improves the previous fastest O(n log3 n) solution. Interestingly, while in undirected planar graphs both min cut and min st-cut have O(n log log n) solutions, in directed planar graphs our result makes min cut faster than min st-cut, which currently requires O(n log n).

In the $k$-dispersion problem, we need to select $k$ nodes of a given graph so as to maximize the minimum distance between any two chosen nodes. This can be seen as a generalization of the independent set problem, where the goal is to select nodes so that the minimum distance is larger than 1. We design an optimal $O(n)$ time algorithm for the dispersion problem on trees consisting of $n$ nodes, thus improving the previous $O(n\log n)$ time solution from 1997. We also consider the weighted case, where the goal is to choose a set of nodes of total weight at least $W$. We present an $O(n\log^2n)$ algorithm improving the previous $O(n\log^4 n)$ solution. Our solution builds on the search version (where we know the minimum distance $λ$ between the chosen nodes) for which we present tight $Θ(n\log n)$ upper and lower bounds.

Labeling schemes seek to assign a short label to each node in a network, so that a function on two nodes (such as distance or adjacency) can be computed by examining their labels alone. For the particular case of trees, following a long line of research, optimal bounds (up to low order terms) were recently obtained for adjacency labeling [FOCS '15], nearest common ancestor labeling [SODA '14], and ancestry labeling [SICOMP '06]. In this paper we obtain optimal bounds for distance labeling. We present labels of size 1/4\log^2n+o(\log^2n), matching (up to low order terms) the recent 1/4\log^2n-\Oh(\log n) lower bound [ICALP '16].

We start a systematic study of data structures for the nearest colored node problem on trees. Given a tree with colored nodes and weighted edges, we want to answer queries (v,c) asking for the nearest node to node v that has color c. This is a natural generalization of the well-known nearest marked ancestor problem. We give an O(n)-space O(log log n)-query solution and show that this is optimal. We also consider the dynamic case where updates can change a node's color and show that in O(n) space we can support both updates and queries in O(log n) time. We complement this by showing that O(polylog n) update time implies Omega(log n \ log log n) query time. Finally, we consider the case where updates can change the edges of the tree (link-cut operations). There is a known (top-tree based) solution that requires update time that is roughly linear in the number of colors. We show that this solution is probably optimal by showing that a strictly sublinear update time implies a strictly subcubic time algorithm for the classical all pairs shortest paths problem on a general graph. We also consider versions where the tree is rooted, and the query asks for the nearest ancestor/descendant of node v that has color c, and present efficient data structures for both variants in the static and the dynamic setting.

We present a (1 + ε)-approximation algorithm running in O ( f (ε) · n log 4 n ) time for finding the diameter of an undirected planar graph with n vertices and with nonnegative edge lengths.

Grammar-based compression, where one replaces a long string by a small context-free grammar that generates the string, is a simple and powerful paradigm that captures (sometimes with slight reduction in efficiency) many of the popular compression schemes, including the Lempel--Ziv family, run-length encoding, byte-pair encoding, Sequitur, and Re-Pair. In this paper, we present a novel grammar representation that allows efficient random access to any character or substring without decompressing the string. Let $S$ be a string of length $N$ compressed into a context-free grammar $\mathcal{S}$ of size $n$. We present two representations of $\mathcal{S}$ achieving $O(\log N)$ random access time, and either $O(n\cdot\alpha_k(n))$ construction time and space on the pointer machine model, or $O(n)$ construction time and space on the RAM. Here, $\alpha_k(n)$ is the inverse of the $k$th row of Ackermann's function. Our representations also efficiently support decompression of any substring in $S$: we can decompress any substring of length $m$ in the same complexity as a single random access query and additional $O(m)$ time. Combining these results with fast algorithms for uncompressed approximate string matching leads to several efficient algorithms for approximate string matching on grammar-compressed strings without decompression. For instance, we can find all approximate occurrences of a pattern $P$ with at most $k$ errors in time $O(n(\min\{|P|k,k^4+|P|\}+\log N)+\mathrm{occ})$, where $\mathrm{occ}$ is the number of occurrences of $P$ in $S$. Finally, we generalize our results to navigation and other operations on grammar-compressed ordered trees. All of the above bounds significantly improve the currently best known results. To achieve these bounds, we introduce several new techniques and data structures of independent interest, including a predecessor data structure, two “biased” weighted ancestor data structures, and a compact representation of heavy paths in grammars.

When designing a preemptive online algorithm for the maximum matching problem, we wish to maintain a valid matching M while edges of the underlying graph are presented one after the other. When presented with an edge e, the algorithm should decide whether to augment the matching M by adding e (in which case e may be removed later on) or to keep M in its current form without adding e (in which case e is lost for good). The objective is to eventually hold a matching M with maximum weight. The main contribution of this paper is to establish new lower and upper bounds on the competitive ratio achievable by preemptive online algorithms: - We provide a lower bound of 1 + ln 2 \approx 1.693 on the competitive ratio of any randomized algorithm for the maximum cardinality matching problem, thus improving on the currently best known bound of e / (e-1) \approx 1.581 due to Karp, Vazirani, and Vazirani [STOC'90]. - We devise a randomized algorithm that achieves an expected competitive ratio of 5.356 for maximum weight matching. This finding demonstrates the power of randomization in this context, showing how to beat the tight bound of 3 + 2\sqrt{2} \approx 5.828 for deterministic algorithms, obtained by combining the 5.828 upper bound of McGregor [APPROX'05] and the recent 5.828 lower bound of Varadaraja [ICALP'11].

A distance sensitivity oracle of an n -vertex graph G = ( V , E ) is a data structure that can report shortest paths when edges of the graph fail. A query ( u ∈ V , v ∈ V , S ⊆ E ) to this oracle returns a shortest u -to- v path in the graph G ′ = ( V , E ∖ S ). We present randomized (Monte Carlo) algorithms for constructing a distance sensitivity oracle of size Õ ( n 3−α ) for | S | = O (lg n /lg lg n ) and any choice of 0 < α < 1. For real edge-lengths, the oracle is constructed in O ( n 4−α ) time and a query to this oracle takes Õ ( n 2−2(1−α)/|S| ) time. For integral edge-lengths in {− M ,..., M }, using the current ω < 2.376 matrix multiplication exponent, the oracle is constructed in O ( Mn 3.376−α ) time with Õ ( n 2−(1−α)/|S| ) query, or alternatively in O ( M 0.681 n 3.575−α ) time with Õ ( n 2−2(1−α)/|S| ) query. Distance sensitivity oracles generalize the replacement paths problem in which u and v are known in advance and | S | = 1. In other words, if P is a shortest path from u to v in G , then the replacement paths problem asks to compute, for every edge e on P , a shortest u -to- v path that avoids e . Our new technique for constructing distance sensitivity oracles using fast matrix multiplication also yields the first subcubic-time algorithm for the replacement paths problem when the edge-lengths are small integers. In particular, it yields a randomized (Monte Carlo) Õ ( Mn 2.376 + M 2 3 n 2.584 )-time algorithm for the replacement paths problem assuming M ≤ n 0.624 . Finally, we mention that both our replacement paths algorithm and our distance sensitivity oracle can be made to work, in the same time and space bounds, for the case of failed vertices rather than edges, that is, when S is a set of vertices and we seek a shortest u -to- v path in the graph obtained from G by removing all vertices in S and their adjacent edges.

In the packed string matching problem, each machine word accomodates alpha characters, thus an n-character text occupies n/alpha memory words. We extend the Crochemore-Perrin constant-space O(n)-time string matching algorithm to run in optimal O(n/alpha) time and even in real-time, achieving a factor alpha speedup over traditional algorithms that examine each character individually. Our solution can be efficiently implemented, unlike prior theoretical packed string matching work. We adapt the standard RAM model and only use its AC0 instructions (i.e. no multiplication) plus two specialized AC0 packed string instructions. The main string-matching instruction is available in commodity processors (i.e. Intel's SSE4.2 and AVX Advanced String Operations); the other maximal-suffix instruction is only required during pattern preprocessing. In the absence of these two specialized instructions, we propose theoretically-efficient emulation using integer multiplication (not AC0) and table lookup.

Let S be a string of length N compressed into a context-free grammar S of size n. We present two representations of S achieving O(log N) random access time, and either O(n · αk(n)) construction time and space on the pointer machine model, or O(n) construction time and space on the RAM. Here, αk(n) is the inverse of the kth row of Ackermann's function. Our representations also efficiently support decompression of any substring in S: we can decompress any substring of length m in the same complexity as a single random access query and additional O(m) time. Combining these results with fast algorithms for uncompressed approximate string matching leads to several efficient algorithms for approximate string matching on grammar-compressed strings without decompression. For instance, we can find all approximate occurrences of a pattern P with at most k errors in time O(n(min{|P|k, k +|P|} +log N) + occ), where occ is the number of occurrences of P in S. Finally, we are able to generalize our results to navigation and other operations on grammar-compressed trees. All of the above bounds significantly improve the currently best known results. To achieve these bounds, we introduce several new techniques and data structures of independent interest, including a predecessor data structure, two “biased” weighted ancestor data structures, and a compact representation of heavy-paths in grammars.

Let G be a directed edge-weighted graph and let P be a shortest path from s to t in G. The replacement paths problem asks to compute, for every edge e on P, the shortest s-to-t path that avoids e. Apart from approximation algorithms and algorithms for special graph classes, the naive solution to this problem - removing each edge e on P one at a time and computing the shortest s-to-t path each time - is surprisingly the only known solution for directed weighted graphs, even when the weights are integrals. In particular, although the related shortest paths problem has benefited from fast matrix multiplication, the replacement paths problem has not, and still required cubic time. For an n-vertex graph with integral edge-lengths between -M and M, we give a randomized algorithm that uses fast matrix multiplication and is sub-cubic for appropriate values of M. We also show how to construct a distance sensitivity oracle in the same time bounds. A query (u,v,e) to this oracle requires sub-quadratic time and returns the length of the shortest u-to-v path that avoids the edge e. In fact, for any constant number of edge failures, we construct a data structure in sub-cubic time, that answer queries in sub-quadratic time. Our results also apply for avoiding vertices rather than edges.

We give an $O(n\log n)$ algorithm for computing the girth (shortest cycle) of an undirected n-vertex planar graph. Our solution extends to any graph of bounded genus. This improves upon the best previously known algorithms for this problem.

We give an O ( n log 2 n )-time, linear-space algorithm that, given a directed planar graph with positive and negative arc-lengths, and given a node s , finds the distances from s to all nodes.

We give an O(n log2 n)-time, linear-space algorithm that, given a directed planar graph with positive and negative arc-lengths, and given a node s, finds the distances from s to all nodes. The best previously known algorithm requires O(nlog3 n) time and O(n log n) space.

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.

The edit distance between two ordered rooted trees with vertex labels is the minimum cost of transforming one tree into the other by a sequence of elementary operations consisting of deleting and relabeling existing nodes, as well as inserting new nodes. In this article, we present a worst-case O ( n 3 )-time algorithm for the problem when the two trees have size n , improving the previous best O ( n 3 log n )-time algorithm. Our result requires a novel adaptive strategy for deciding how a dynamic program divides into subproblems, together with a deeper understanding of the previous algorithms for the problem. We prove the optimality of our algorithm among the family of decomposition strategy algorithms—which also includes the previous fastest algorithms—by tightening the known lower bound of Ω( n 2 log 2 n ) to Ω( n 3 ), matching our algorithm's running time. Furthermore, we obtain matching upper and lower bounds for decomposition strategy algorithms of Θ( nm 2 (1 + log n / m )) when the two trees have sizes m and n and m < n .