Counting Short Cycles in Bipartite Graphs: A Fast Technique/Algorithm and a Hardness Result

In this paper, we propose a new technique, based on the so-called breadth-first search algorithm, to count the short cycles of a bipartite graph. For a general bipartite graph with vertical bar V vertical bar nodes and girth g, our technique has a time complexity of O(vertical bar V vertical bar(2) Delta) to count g-cycles and (g + 2)-cycles, and a time complexity of O(vertical bar V vertical bar(2) Delta(2)) to count (g + 4)-cycles, where Delta is the maximum node degree in the graph. Moreover, for bi-regular bipartite graphs, the latter complexity is further reduced to O(vertical bar V vertical bar(2) Delta). Compared to the fastest known algorithm, which has a complexity O(g vertical bar V vertical bar(2) Delta(2)), the proposed method always has a lower complexity for counting g-cycles and (g+ 2)-cycles. It also has a lower complexity for counting (g + 4)-cycles in bi-regular graphs and in scenarios where g is increased with the size of the graph. Related to the problem of counting short cycles, we also demonstrate, using a long-standing conjecture, that there is no algorithm with time complexity less than O(vertical bar V vertical bar(2-2/1+i)) that can determine whether a given sparse bipartite graph has a cycle of length 4i. An important application of the results presented here is to count the short cycles of Tanner graphs of low-density parity-check (LDPC) codes.