A Truly Subcubic Combinatorial Algorithm for Induced 4-Cycle Detection
Abstract
In this paper, we present the first truly subcubic, combinatorial algorithm for detecting an induced 4-cycle in a graph. The running time is \(O(n^{2.84})\) on \(n\)-node graphs, thus separating the task of detecting induced 4-cycles from detecting triangles, which requires \(n^{3.o(1)}\) time combinatorially under the popular Boolean Matrix Multiplication hypothesis.
Fields of Study & Subjects
Interconnection Networks and Systems
Advanced Graph Theory Research
graph theory and CDMA systems
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Pages
- 3562–3599
- Publication date
- 1 January 2026
- Language
- EN