Improved Girth Approximation and Roundtrip Spanners

Shiri Chechik, Yang P. Liu, Omer Rotem, Aaron Sidford

Introduction

The girth of a graph—the length of its shortest cycle—is a fundamental structural property in graph theory. While computing the exact girth of an undirected graph is well-understood, directed graphs present a significant algorithmic challenge. In weighted directed graphs, finding the exact girth requires $O(mn)$ time, a complexity bound tied to the All-Pairs Shortest Paths (APSP) problem. Given that a truly subcubic algorithm for APSP remains one of the most significant open problems in computer science, researchers have turned to approximation algorithms to achieve subquadratic runtimes.

This paper introduces the first subquadratic-time algorithms for approximating the girth of directed graphs to within a constant factor. By developing novel randomized pruning and deterministic ball-growing techniques, the authors also provide state-of-the-art constructions for roundtrip spanners, effectively narrowing the performance gap between directed and undirected graph algorithms.

The Roundtrip Challenge

In undirected graphs, girth can be efficiently approximated using spanners—sparse subgraphs that preserve distances within a multiplicative factor. However, directed graphs are inherently more complex due to the asymmetry of distances; the distance from $u$ to $v$ does not necessarily equal the distance from $v$ to $u$. To address this, researchers utilize "roundtrip spanners," which aim to preserve the roundtrip distance $d(u, v) + d(v, u)$.

Prior to this work, fast algorithms for directed graphs were limited to $O(k \log n)$ approximations. This research seeks to achieve a constant-factor approximation in subquadratic time while reducing or eliminating the reliance on randomness.

Algorithmic Framework

The authors propose three primary algorithmic strategies to tackle the girth approximation problem:

1. Randomized Pruning for 3-Approximation

To achieve a 3-multiplicative approximation in $\tilde{O}(m\sqrt{n})$ time, the authors employ a randomized similarity test. By sampling $\tilde{O}(\sqrt{n})$ vertices and computing distances to and from them, the algorithm identifies potential short cycles. If no cycle is found immediately, the distances are used to prune the search space. Specifically, the algorithm only retains vertices in a node’s "outball" if they maintain a specific proximity to other nodes within that ball. This pruning reduces the candidate pool for short cycles to $\tilde{O}(\sqrt{n})$ per node, enabling a rapid local search.

2. Deterministic Overlapping Ball-Growing

A common technique in graph algorithms is partitioning the graph into disjoint sets. However, in directed graphs, such partitions often break roundtrip cycles. The authors introduce a deterministic approach that grows "inballs" and "outballs" around vertices, allowing these partitions to overlap at the boundaries. By identifying a "good cut"—where the volume of the ball does not expand too rapidly—the algorithm can recurse on the boundary and safely delete the inner ball without losing critical roundtrip information. This leads to an $O(k \log \log n)$ approximation.

3. The Hybrid Approach

By combining the randomized similarity testing with the deterministic ball-growing technique, the authors achieve an $O(k \log k)$ approximation in $\tilde{O}(m^{1+1/k})$ time. This hybrid method more effectively controls the growth of the balls, optimizing the trade-off between the approximation factor and the sparsity of the resulting spanner.

Key Insights

The success of these algorithms rests on two primary insights:

  • The Similarity Constraint: If a vertex $v$ is part of a cycle of length $R$, any vertex in close proximity to $v$ must also be relatively close to the entire cycle. This geometric property allows for aggressive pruning without the risk of deleting the shortest cycle.
  • Overlapping Partitions: Unlike undirected graphs where disjoint partitions are standard, directed roundtrip distances require overlapping boundaries during recursion. This preserves the integrity of cycles that would otherwise be severed by a hard cut.

Results and Significance

The paper establishes several landmark results in algorithmic graph theory:

  • First Constant-Factor Approximation: A randomized algorithm providing a 3-approximation of the girth in $\tilde{O}(m\sqrt{n})$ time, breaking the $O(mn)$ APSP barrier.
  • Sparse Spanners: Construction of an 8-multiplicative roundtrip spanner with $\tilde{O}(n^{3/2})$ edges in $\tilde{O}(m\sqrt{n})$ time.
  • Deterministic Breakthroughs: The first deterministic, nearly linear time algorithm for $O(k \log \log n)$ approximations.

Future Directions

Despite these advancements, the "spanner barrier" remains: currently, all fast girth approximations for directed graphs are dependent on roundtrip spanner construction. Future research may focus on circumventing this dependency to achieve even faster runtimes. Additionally, closing the gap to reach a deterministic $O(k)$ approximation—matching the standard for undirected graphs—remains a significant open challenge. Finally, the authors suggest that these routines could be integrated with parallel reachability advances to develop highly efficient parallel algorithms for girth estimation.

Summary updated

BibTeX
@inproceedings{chechik2020improved,
  author = {Shiri Chechik and Yang P. Liu and Omer Rotem and Aaron Sidford},
  title = {{Improved Girth Approximation and Roundtrip Spanners}},
  booktitle = {STOC},
  year = {2020},
  doi = {10.1145/3357713.3384330},
}
Figure