Approximation Algorithms for Min-Distance Problems in DAGs

Mina Dalirrooyfard, Jenny Kaufmann

Abstract

This paper investigates the computational complexity of min-distance problems in Directed Acyclic Graphs (DAGs). Traditional distance metrics often fail in DAGs due to the lack of paths between arbitrary nodes. The authors propose the use of min-distance, defined as $d_{min}(u, v) = \min(d(u, v), d(v, u))$, and develop new approximation algorithms for min-diameter, min-radius, and min-eccentricities. By leveraging topological partitioning and sparse matrix multiplication, the authors provide algorithms that are conditionally tight under standard complexity conjectures, significantly improving upon previous bounds.

Introduction

In a Directed Acyclic Graph (DAG), standard distance measures are frequently unhelpful because edges only flow in one direction. Consequently, there is often no path between two arbitrary nodes, rendering their distance infinite. To address this, researchers utilize the min-distance: $d_{min}(u, v) = \min(d(u, v), d(v, u))$. This metric represents the shortest path in whichever direction a path actually exists, making it useful for real-world applications such as logistics and network analysis.

However, computing min-distances exactly is computationally expensive, as it is equivalent to the All-Pairs Shortest Paths (APSP) problem. For large graphs, APSP is prohibitively slow. This research seeks to find approximation algorithms that run in subquadratic time (faster than $n^2$) while maintaining a low error factor.

Methodology

The authors employ several sophisticated techniques to bypass the fact that min-distance does not obey the triangle inequality, a property most graph algorithms rely on:

  • Topological Partitioning: By sorting the DAG's vertices and partitioning them into consecutive intervals, the authors can perform local searches and use "jumping-off points" to estimate distances to distant parts of the graph.
  • Recursive Approximation: For min-radius and eccentricities, a recursive approach is used. Instead of running a full APSP, the approximation is applied recursively on smaller intervals, significantly improving runtime.
  • Sparse Matrix Multiplication: For the min-diameter problem in dense graphs, the authors leverage the Yuster-Zwick algorithm for sparse matrix multiplication to detect path intersections more efficiently than standard BFS or Dijkstra's would allow.
  • Fine-Grained Reductions: To prove optimality, the authors use reductions from well-known hard problems like Triangle Detection, the Strong Exponential Time Hypothesis (SETH), and the Orthogonal Vectors (OV) Conjecture.

Key Results

The paper provides a suite of new bounds that close long-standing theoretical gaps. The primary contributions include a 2-approximation for min-radius and a near-3/2-approximation for min-diameter in dense graphs. These results are summarized in the table below.

Table 1: Comparison of upper and lower bounds for min-distance problems.

Key insights from these results include:

  • Exploiting DAG Structure: The inherent topological order of a DAG provides a structure that can be exploited via binary search and interval partitioning, compensating for the lack of triangle inequality.
  • Closing the Gap for Min-Radius: Previous work offered a 3-approximation for min-radius. This paper improves that to a 2-approximation and proves that a $(2-\delta)$-approximation would require a breakthrough in Triangle Detection, effectively "solving" the problem's complexity.
  • Dense vs. Sparse Graphs: The difficulty of these problems varies with graph density. The paper provides the first "near-3/2" approximation for min-diameter specifically optimized for dense graphs, running faster than the best-known APSP algorithms.

Conclusion and Future Work

This work establishes near-optimal approximation factors for several fundamental min-distance problems in DAGs. However, some challenges remain. While the bounds for dense graphs have been tightened, a gap still exists between the upper and lower bounds for the min-diameter of sparse DAGs. Additionally, some of the fastest results rely on algebraic methods (fast matrix multiplication), which can be difficult to implement efficiently in practice compared to combinatorial algorithms. Future research may focus on eliminating additive errors in the min-diameter algorithm and exploring purely combinatorial approaches for these problems.

Summary updated

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 min-distance. 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. As with the standard distance problems, the Strong Exponential Time Hypothesis [Impagliazzo-Paturi-Zane 2001, Calabro-Impagliazzo-Paturi 2009] leaves little hope for computing min-distance 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 min-distance 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 min-diameter, min-radius and min-eccentricities. Abboud et al obtained a 3-approximation algorithm for min-radius on DAGs which works in Õ(m√n) time, and showed that any (2-δ)-approximation requires n^{2-o(1)} time for any δ > 0, under the Hitting Set Conjecture. We close the gap, obtaining a 2-approximation 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 2-approximation algorithm for min-diameter along with a lower bound stating that any (3/2-δ)-approximation algorithm for sparse DAGs requires n^{2-o(1)} time under SETH. We close this gap for dense DAGs by obtaining a 3/2-approximation 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
@inproceedings{dalirrooyfard2021approximation,
  author = {Mina Dalirrooyfard and Jenny Kaufmann},
  title = {{Approximation Algorithms for Min-Distance Problems in DAGs}},
  booktitle = {ICALP},
  year = {2021},
  url = {https://openreview.net/forum?id=XT9ok-LoKs},
}
Figure