This paper introduces a new technique that generalizes previously known fine-grained reductions
from linear structures to graphs. Least Weight Subsequence (LWS) is a class of highly sequential
optimization problems with form F(j) = mini<j[F(i) + ci,j 10 ] . They can be solved in quadratic
time using dynamic programming, but it is not known whether these problems can be solved faster
than n2?o(1) time. Surprisingly, each such problem is subquadratic time reducible to a highly
parallel, non-dynamic programming problem [KPS17]. In other words, if a “static” problem is faster
than quadratic time, so is an LWS problem. For many instances of LWS, the sequential versions are
equivalent to their static versions by subquadratic time reductions. The previous result applies to
LWS on linear structures, and this paper extends this result to LWS on paths in sparse graphs, the
Least Weight Subpath (LWSP) problems. When the graph is a multitree (i.e. a DAG where any pair
of vertices can have at most one path) or when the graph is a DAG whose underlying undirected
graph has constant treewidth, we show that LWSP on this graph is still subquadratically reducible
to their corresponding static problems. For many instances, the graph versions are still equivalent
to their static versions.
Moreover, this paper shows that if we can decide a property of form $\exists x \exists y P(x, y)$ in subquadratic
time, where P is a quickly checkable property on a pair of elements, then on these classes of graphs,
we can also in subquadratic time decide whether there exists a pair x, y in the transitive closure of
the graph that also satisfy P(x, y).

In the proceedings of IPEC2019

Least Weight Subsequence (LWS) is a type of highly sequential optimization problems with form $F(j) = \min_{i < j} [F(i) + c_{i,j}]$. They can be solved in quadratic time using dynamic programming, but it is not known whether these problems can be solved faster than $n^{2-o(1)}$ time. Surprisingly, each such problem is subquadratic time reducible to a highly parallel, non-dynamic programming problem [KPS17]. In other words, if a "static" problem is faster than quadratic time, so is an LWS problem. For many instances of LWS, the sequential versions are equivalent to their static versions by subquadratic time reductions. The previous result applies to LWS on linear structures, and this paper extends this result to LWS on paths in sparse graphs. When the graph is a multitree (i.e. a DAG where any pair vertices can have at most one path) or when the graph is a DAG whose underlying undirected graph has constant treewidth, we show that LWS on this graph is still subquadratically reducible to their corresponding static problems. For many instances, the graph versions are still equivalent to their static versions.

Moreover, this paper shows that on these graphs, property testing of form $\exists x \exists y (\text{TC}_E(x,y) \wedge P(x,y))$ is subquadratically reducible to property testing of form $\exists x \exists y P(x,y)$, where $P$ is a property checkable in time linear to the sizes of $x$ and $y$, and $\text{TC}_E$ is the transitive closure of relation $E$. Furthermore, when $P$ is definable by a first-order logic formula with at most one quantified variable, then the above two problems are equivalent to each other by subquadratic reductions.