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.
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