Two Algorithms Pertaining to s to t

This dissertation compiles together (with some revisions) some of my works whose algorithms are concerned with n vertex m edge digraphs $G=(V,E)$ and paths within them (say from $s in V$ to $t in V$). We first discuss the restricted shortest paths problem where edges of G are assigned two non-negative weights: lengths and costs. For a fixed source $s in V$ and a cost threshold D we wish to find, for each target $t in V$, the length of the shortest $(s,t)$-path whose total cost is at most D. This problem is NP-hard --- for instance, the $0$-$1$ knapsack problem is a special case where G is a dipath --- hence the focus on finding approximate solutions for the past 20 or so years. We give the first sub-$mn$ time $(1+varepsilon, 1+varepsilon)$-approximation algorithm for digraphs, where both the length-optimality and cost-constraint may be off by a multiplicative $(1+varepsilon)$ factor for an arbitrary constant $varepsilon > 0$. This answers a problem posed by Bernstein in 2012 after his breakthrough in the undirected case. Next, we turn to algorithmic versions of the so-called folklore shortcut set (and hopset), which is a set of edges H such that $G cup H$ has the exact same reachability relations as G, but shortest paths in $G cup H$ use no more than n¹⁺ᵒ⁽¹⁾/sqrt|H| edges. Close to 30 years after its conception, Jambulapati, Liu, and Sidford gave the first near-linear time construction for $|H| approx n$. In a perfect world scenario where the matrix multiplication exponent $omega = 2$, we complete this picture for n lesssim |H| lesssim n². In the world we live in right now (2026), or even in a Pre-Strassen age where $omega le 3$ (before 1969), our result still leads to a near-linear time construction of a shortcut set closer in parameters to the folklore. Like prior work, this is designed to parallelize, which then leads to faster work-efficient parallel algorithms for single-source reachability and shortest paths when $m gg n$. Both algorithms use sparsification, but in a somewhat oblique way (typically, the input graph is sparsified); the first algorithm sparsifies an algorithm, and the second algorithm sparsifies a proof object.