Complexity of Counting Cycles using Zeons
Résumé
Nilpotent adjacency matrix methods are employed to count k-cycles in simple graphs on n vertices for any k <= n. The worst-case time complexity of counting k-cycles in an n-vertex simple graph is shown to be O(n(alpha+1)2(n)) where alpha <= 3 is the exponent representing the complexity of matrix multiplication. When k is fixed, the counting of all k-cycles in an n-vertex graph is of time complexity O (n(alpha+k-1)). Letting Omega = ((n)(2)), the average-case time complexity of counting k-cycles in an n-vertex, e-edge graph where e <= q (Omega/k - 1) for fixed 0 < q < 1 is found to be O(n(4)(1 + q)(n)). The storage complexity of the approach detailed herein is O(n(2)2(n)). For reference, experimental results detailing computation times (in seconds) are included alongside similar computations performed with algorithms based on the approaches of Bax and Tarjan