An efficient approximation algorithm for counting n-cycles in a graph

摘要

Recently, Cash [G.G. Cash, The number of n-cycles in a graph, Applied Mathematics and Computation 184 (2007) 1080–1083] presents a method for counting the number of n-cycles in a graph. However, we point out that all methods for (precisely) counting n-cycles, including Cash’s, are super-polynomial-time, unless P = NP. This implies that it is unlikely to count n-cycles both precisely and efficiently. To solve this problem, we propose an efficient approximation algorithm. Our algorithm is guaranteed to finish in polynomial-time and has a reasonable error bound.