On the complexity of cycle enumeration using Zeons

Overview & Synopsis

Nilpotent adjacency matrix methods are employed to enumerate $k$-cycles in simple graphs on $n$ vertices for any $k\le n$. The worst-case time complexity of counting $k$-cycles in an $n$-vertex simple graph is shown to be $\mathcal{O}(n^{\alpha+1} 2^{n})$, where $\alpha\le 3$ is the exponent representing the complexity of matrix multiplication. When $k$ is fixed, the enumeration of all $k$-cycles in an $n$-vertex graph is of time complexity $\mathcal{O}(n^{\alpha+k-1})$. Letting $\Omega=\binom{n}{2}$, the average-case time complexity of counting $k$-cycles in an $n$-vertex, $e$-edge graph where $e\le \displaystyle q\left(\frac{\Omega}{k}-1\right)$ for fixed $0