2019/12/25 by Ali Dehghan, Amir H. Banihashemi
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced Graph Theory Research #DNA and Biological Computing #Error Correcting Code Techniques
paper · doi:10.1109/tcomm.2019.2962397
openalex publication_date 2019/12/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
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 |V| nodes and girth g, our technique has a time complexity of O(|V|2Δ) to count g-cycles and (g + 2)-cycles, and a time complexity of O(|V|2Δ2) to count (g + 4)-cycles, where Δ is the maximum node degree in the graph. Moreover, for bi-regular bipartite graphs, the latter complexity is further reduced to O(|V|2Δ). Compared to the fastest known algorithm, which has a complexity O(g|V|2Δ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(|V|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.