# Amortized tildeO(|V|)-Delay Algorithm for Listing Chordless Cycles in Undirected Graphs

arXiv: https://arxiv.org/abs/1408.1265 · HTML: https://mlsanity.com/paper/1408.1265/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Aug 2014.

## Built on by (most cited first, 5 of 5)

- [Weisfeiler and Lehman Go Cellular: CW Networks](https://mlsanity.com/paper/2106.12575/) (2021)
- [Cell Attention Networks](https://mlsanity.com/paper/2209.08179/) (2022)
- [P-Tensors: a General Formalism for Constructing Higher Order Message Passing Networks](https://mlsanity.com/paper/2306.10767/) (2023)
- [CellCLAT: Preserving Topology and Trimming Redundancy in Self-Supervised Cellular Contrastive Learning](https://mlsanity.com/paper/2505.21587/) (2025)
- [HTG-GCL: Leveraging Hierarchical Topological Granularity from Cellular Complexes for Graph Contrastive Learning](https://mlsanity.com/paper/2512.02073/) (2025)

## Abstract (arXiv)

Chordless cycles are very natural structures in undirected graphs, with an important history and distinguished role in graph theory. Motivated also by previous work on the classical problem of listing cycles, we study how to list chordless cycles. The best known solution to list all the C chordless cycles contained in an undirected graph G = (V,E) takes O(|E|2 +|E|· C) time. In this paper we provide an algorithm taking tildeO(|E| + |V |· C) time. We also show how to obtain the same complexity for listing all the P chordless st-paths in G (where C is replaced by P ).