On the complexity of cycle enumeration using Zeons

René Schott (1, 2) , Stacey Staples (3)

1 IECN - Institut Élie Cartan de Nancy
2 LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
3 Department of Mathematics and Statistics - Southern Illinois University

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

Mots clés: Cycles; Enumeration; Complexity; Zeons

Domaines: Combinatoire [math.CO]; Algèbres d'opérateurs [math.OA]

René Schott, Stacey Staples. On the complexity of cycle enumeration using Zeons. 2010. ⟨hal-00567889⟩