Improved message-passing algorithm for counting short cycles in bipartite graphs

Recently, Karimi and Banihashemi proposed an algorithm based on message-passing to count cycles in a graph of lengths less than double its girth. The algorithm uses only integer additions and subtractions to compute messages at the nodes of the graph that are passed to adjacent nodes. The complexity of the algorithm, when applied to a bipartite graph of girth g that has E edges, is O(gE²). The algorithm is superior to many other existing algorithms in the literature. In this paper, an improvement of this algorithm is presented that cuts both the complexity and the computing time by a factor of two. The improved algorithm is also applied to Tanner graphs of quasi-cyclic codes and, in this case, the complexity can be further cut by a factor of p, where p is the size of the circulants in the parity-check matrix of the quasi-cyclic code.