The Fine-Grained Complexity of Min-Distance Problems in DAGs

Abstract

The min-distance between two nodes u and v is the minimum of the shortest path distances from u to v and from v to u. Min-distance is a natural measure of distance in DAGs (directed acyclic graphs), and many classically studied graph distance parameters can be redefined in terms of mindistance. This thesis presents several new results on the fine-grained complexity of approximating min-distance parameters such as min-diameter, min-radius, and min-eccentricities, concentrating primarily (though not exclusively) on the special case of DAGs. In particular, we develop new approximation algorithms for these parameters, with runtimes polynomially faster than the standard All-Pairs Shortest Paths algorithm. Our algorithms improve on the approximation factors achieved in prior work, and in several cases, we obtain approximation factors that are conditionally tight, in the sense that they match lower bounds implied by hardness hypotheses such as the Orthogonal Vectors Conjecture and the Hitting Set Conjecture. We also obtain new several conditional lower bounds for min-distance problems, including a new lower bound for min-diameter conditioned on the OV Conjecture. Lastly, we present the first study of approximating bichromatic min-diameter.