Dalirrooyfard, Mina ;
Kaufmann, Jenny
Approximation Algorithms for MinDistance Problems in DAGs
Abstract
Graph parameters such as the diameter, radius, and vertex eccentricities are not defined in a useful way in Directed Acyclic Graphs (DAGs) using the standard measure of distance, since for any two nodes, there is no path between them in one of the two directions. So it is natural to consider the distance between two nodes as the length of the shortest path in the direction in which this path exists, motivating the definition of the mindistance. The mindistance between two nodes u and v is the minimum of the shortest path distances from u to v and from v to u.
As with the standard distance problems, the Strong Exponential Time Hypothesis [ImpagliazzoPaturiZane 2001, CalabroImpagliazzoPaturi 2009] leaves little hope for computing mindistance problems faster than computing All Pairs Shortest Paths, which can be solved in Õ(mn) time. So it is natural to resort to approximation algorithms in Õ(mn^{1ε}) time for some positive ε. Abboud, Vassilevska W., and Wang [SODA 2016] first studied mindistance problems achieving constant factor approximation algorithms on DAGs, and Dalirrooyfard et al [ICALP 2019] gave the first constant factor approximation algorithms on general graphs for mindiameter, minradius and mineccentricities. Abboud et al obtained a 3approximation algorithm for minradius on DAGs which works in Õ(m√n) time, and showed that any (2δ)approximation requires n^{2o(1)} time for any δ > 0, under the Hitting Set Conjecture. We close the gap, obtaining a 2approximation algorithm which runs in Õ(m√n) time. As the lower bound of Abboud et al only works for sparse DAGs, we further show that our algorithm is conditionally tight for dense DAGs using a reduction from Boolean matrix multiplication. Moreover, Abboud et al obtained a linear time 2approximation algorithm for mindiameter along with a lower bound stating that any (3/2δ)approximation algorithm for sparse DAGs requires n^{2o(1)} time under SETH. We close this gap for dense DAGs by obtaining a 3/2approximation algorithm which works in O(n^{2.350}) time and showing that the approximation factor is unlikely to be improved within O(n^{ω  o(1)}) time under the high dimensional Orthogonal Vectors Conjecture, where ω is the matrix multiplication exponent.
BibTeX  Entry
@InProceedings{dalirrooyfard_et_al:LIPIcs.ICALP.2021.60,
author = {Dalirrooyfard, Mina and Kaufmann, Jenny},
title = {{Approximation Algorithms for MinDistance Problems in DAGs}},
booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
pages = {60:160:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771955},
ISSN = {18688969},
year = {2021},
volume = {198},
editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14129},
URN = {urn:nbn:de:0030drops141293},
doi = {10.4230/LIPIcs.ICALP.2021.60},
annote = {Keywords: Finegrained complexity, Graph algorithms, Diameter, Radius, Eccentricities}
}
02.07.2021
Keywords: 

Finegrained complexity, Graph algorithms, Diameter, Radius, Eccentricities 
Seminar: 

48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Issue date: 

2021 
Date of publication: 

02.07.2021 