Conditionally Optimal Approximation Algorithms for the Girth of a Directed Graph

Mina Dalirrooyfard, Virginia Vassilevska Williams

Finding the girth, or the length of the shortest cycle, is a fundamental problem in directed graph theory. While exact solutions typically require $O(mn)$ time, this paper establishes that a 2-approximation is the conditionally optimal limit for sub-quadratic time algorithms. We present the first combinatorial 2-approximation algorithm for directed girth running in sub-quadratic time, effectively bridging the gap between existing factor-3 approximations and the theoretical lower bound.

Introduction

The girth of a graph is a basic structural property. In undirected graphs, efficient constant-factor approximations have existed for decades. However, directed graphs present a significantly greater challenge. Calculating the exact girth in a directed graph with $n$ nodes and $m$ edges generally requires running a shortest path algorithm from every node, leading to an $O(mn)$ runtime. For large-scale sparse graphs, this complexity is prohibitive.

Recent breakthroughs, such as the combinatorial 3-approximation by Chechik et al. (2020), have improved the landscape. This work pushes the boundary further, asking whether a 2-approximation is achievable in sub-quadratic time and identifying the fundamental limits of such approximations.

Methods

The research combines fine-grained complexity analysis with novel algorithmic techniques, focusing on two main areas:

1. Conditional Lower Bounds

The authors demonstrate that any algorithm providing a $(2-\epsilon)$-approximation for directed girth in $O(m^{2-\epsilon})$ time would contradict the $k$-Cycle Hypothesis. This hypothesis posits that detecting a cycle of length $k$ cannot be done in sub-quadratic time, suggesting that a factor of 2 is a natural barrier for fast algorithms.

2. Combinatorial Sampling and Pruning

To achieve the 2-approximation, the authors utilize a strategy based on random sampling and distance-constrained search. For graphs with small girth, a sophisticated sampling lemma identifies "representative" sets of nodes. The algorithm then employs a modified BFS or Dijkstra search that prunes the search space based on these samples.

Illustration of the distance properties on a shortest cycle of length $g$ used for the hitting set argument.

As shown in the figure above, if a node $u$ lies on a shortest cycle of length $g$, any node $x$ on that cycle at distance $j$ from $u$ must have a return path of length $g-j$. By sampling nodes (like $y$ in the hitting set) that "cover" these neighborhoods, the algorithm can find the cycle without an exhaustive search of the entire graph.

Key Results

The paper provides several conditionally optimal results for directed girth approximation:

  • Unweighted Graphs: A 2-approximation in $\tilde{O}(mn^{3/4})$ time.
  • Weighted Graphs: A $(2+\epsilon)$-approximation in $\tilde{O}(m\sqrt{n})$ time.
  • Higher Approximation Factors: A $(4+\epsilon)$-approximation in $\tilde{O}(mn^{\sqrt{2}-1})$ time, with generalized $(2k+\epsilon)$-approximations offering even faster runtimes.
  • Roundtrip Spanners: An improved construction of $(5+\epsilon)$-approximate roundtrip spanners with $\tilde{O}(n^{1.5})$ edges, surpassing the previous best factor of 8.

Discussion and Conclusion

This work identifies 2 as the "conditionally optimal" approximation factor for directed girth, providing a definitive target for future algorithmic development. The results are conditional on the $k$-Cycle Hypothesis; a refutation of this hypothesis would necessitate a re-evaluation of these lower bounds. While the current algorithms are randomized, developing deterministic sub-quadratic 2-approximations remains an open challenge. Additionally, further optimization of the running time exponents for approximation factors between 2 and 3 is a promising direction for future research.

Summary updated

Abstract

The girth is one of the most basic graph parameters, and its computation has been studied for many decades. Under widely believed fine-grained assumptions, computing the girth exactly is known to require mn^{1-o(1)} time, both in sparse and dense m-edge, n-node graphs, motivating the search for fast approximations. Fast good quality approximation algorithms for undirected graphs have been known for decades. For the girth in directed graphs, until recently the only constant factor approximation algorithms ran in O(n^ω) time, where ω < 2.373 is the matrix multiplication exponent. These algorithms have two drawbacks: (1) they only offer an improvement over the mn running time for dense graphs, and (2) the current fast matrix multiplication methods are impractical. The first constant factor approximation algorithm that runs in O(mn^{1-ε}) time for ε > 0 and all sparsities m was only recently obtained by Chechik et al. [STOC 2020]; it is also combinatorial. It is known that a better than 2-approximation algorithm for the girth in dense directed unweighted graphs needs n^{3-o(1)} time unless one uses fast matrix multiplication. Meanwhile, the best known approximation factor for a combinatorial algorithm running in O(mn^{1-ε}) time (by Chechik et al.) is 3. Is the true answer 2 or 3? The main result of this paper is a (conditionally) tight approximation algorithm for directed graphs. First, we show that under a popular hardness assumption, any algorithm, even one that exploits fast matrix multiplication, would need to take at least mn^{1-o(1)} time for some sparsity m if it achieves a (2-ε)-approximation for any ε > 0. Second we give a 2-approximation algorithm for the girth of unweighted graphs running in Õ(mn^{3/4}) time, and a (2+ε)-approximation algorithm (for any ε > 0) that works in weighted graphs and runs in Õ(m√ n) time. Our algorithms are combinatorial. We also obtain a (4+ε)-approximation of the girth running in Õ(mn^{√2-1}) time, improving upon the previous best Õ(m√n) running time by Chechik et al. Finally, we consider the computation of roundtrip spanners. We obtain a (5+ε)-approximate roundtrip spanner on Õ(n^{1.5}/ε²) edges in Õ(m√n/ε²) time. This improves upon the previous approximation factor (8+ε) of Chechik et al. for the same running time.
BibTeX
@inproceedings{dalirrooyfard2020conditionally,
  author = {Mina Dalirrooyfard and Virginia Vassilevska Williams},
  title = {{Conditionally Optimal Approximation Algorithms for the Girth of a Directed Graph}},
  booktitle = {ICALP},
  year = {2020},
  url = {https://openreview.net/forum?id=aPJrksWkYZw},
}
Figure