Abstract
This paper introduces a new technique that generalizes previously known finegrained reductions from linear structures to graphs. Least Weight Subsequence (LWS) [Hirschberg and Larmore, 1987] is a class 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^{2o(1)} time. Surprisingly, each such problem is subquadratic time reducible to a highly parallel, nondynamic programming problem [Marvin Künnemann et al., 2017]. 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).
BibTeX  Entry
@InProceedings{gao:LIPIcs:2019:11477,
author = {Jiawei Gao},
title = {{On the FineGrained Complexity of Least Weight Subsequence in Multitrees and Bounded Treewidth DAGs}},
booktitle = {14th International Symposium on Parameterized and Exact Computation (IPEC 2019)},
pages = {16:116:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771290},
ISSN = {18688969},
year = {2019},
volume = {148},
editor = {Bart M. P. Jansen and Jan Arne Telle},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11477},
URN = {urn:nbn:de:0030drops114778},
doi = {10.4230/LIPIcs.IPEC.2019.16},
annote = {Keywords: finegrained complexity, dynamic programming, graph reachability}
}
Keywords: 

finegrained complexity, dynamic programming, graph reachability 
Collection: 

14th International Symposium on Parameterized and Exact Computation (IPEC 2019) 
Issue Date: 

2019 
Date of publication: 

04.12.2019 