Efficient String and Graph Algorithms in Modern Settings

Abstract

Fundamental computer science problems such as edit distance have been well-studied for decades, and algorithms for these problems have become established and widespread. In modern times, however, achieving even faster algorithms for more specific scenarios finds increasing value as dataset sizes become larger and computer application settings become more varied. While a polynomial-time solution in the static sequential setting may be known and straightforward to implement, it may not be quick in an online setting or take advantage of structural properties inherent to the problem setting that could lead to a more efficient solution. Parameterized algorithms and algorithms specifically designed for parallel or dynamic settings help address these gaps in algorithm utility and understanding, bringing a fresh lens to old problems.

In this work, we start by studying algorithms for string, tree, and Dyck edit distance with runtimes parameterized by the distance itself, termed the ``bounded-distance'' regime. We begin by giving an O(n + poly(k))-time algorithm for tree edit distance, answering a longstanding open question on the existence of such an algorithm (where k represents the distance). Expanding on our tree edit distance approach, we then give the first O(n + poly(k))-time algorithms for weighted string, weighted tree, and weighted Dyck edit distance.

Beyond the bounded-distance regime, we give dynamic solutions for tree and Dyck edit distance. For each, we provide novel dynamic reductions to string edit distance matching state-of-the-art approximation factors from the static setting. To do so, we utilize a novel dynamic heavy-light decomposition implementation of our own complemented by a dynamic strings data structure from the literature.

Finally, we consider edit distance and related string problems in the Massively Parallel Computations (MPC) model. We give an approximation algorithm for edit distance in subpolynomial rounds with subpolynomial approximation factor, and conjecture on the hardness of the problem in MPC. We then end with constant-round MPC algorithms for longest palindrome, longest common substring, and suffix tree construction.