Search

The problem of finding bipartite (Tanner) graphs with given degree sequences that have large girth and few short cycles is of great interest in many applications including construction of good low-density parity-check (LDPC) codes. In this paper, we prove that for given integers $\alpha $ , $\beta $ , and $\gamma $ , and degree sequences $\pi $ and $\pi '$ , the problem of determining whether there exists a simple bipartite graph with degree sequences $(\pi, \pi ')$ that has at most $\alpha $ ($\beta $ and $\gamma $) cycles of length four (six and eight, respectively) is NP-complete. This is proved by a two-step polynomial-time reduction from the 3-Partition Problem. On the other hand, using connections to linear hypergraphs, we prove that given the degree sequence $\pi $ , a polynomial time algorithm can be devised to determine whether there exists a bipartite graph whose degree sequence on one side of the bipartition is $\pi $ and has a girth of at least six. In addition to these complexity results, we devise a quasi-polynomial time algorithm that can construct a bipartite graph with given (irregular) degree sequences and a girth that increases logarithmically with the size of the graph. Compared to the well-known progressive-edge-growth (PEG) algorithm, the proposed method, in some cases, results in Tanner graphs with larger girth, particularly for scenarios where the degree sequences of the graph are strictly enforced. [ABSTRACT FROM AUTHOR]

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 $\mathcal {O}(|V|^{2}\Delta)$ to count $g$ -cycles and $(g+2)$ -cycles, and a time complexity of $\mathcal {O}(|V|^{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 $\mathcal {O}(|V|^{2}\Delta)$. Compared to the fastest known algorithm, which has a complexity $\mathcal {O}(g |V|^{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 $\mathcal {O}\left({|V|^{2-\frac {2}{1+i}}}\right)$ 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. [ABSTRACT FROM AUTHOR]

In this paper, we give lower bounds on the size of $(a,b)$ elementary trapping sets (ETSs) of variable-regular LDPC codes with any girth, $g$ , and irregular ones with girth 8, where $a$ is the size and $b$ is the number of degree-one check nodes. Our proposed lower bounds are analytical, applicable to all values of $g$ and $b$ , based on graph theories and tighter than the existing ones in the literature. Our results mostly depend on the girth. We also propose results, which are independent of the girth and rely on the variables $a$ , $b$ , $\gamma $ , and the column weight value. We obtain the tightest lower bounds on the size of ETSs of variable-regular LDPC codes with girth eight. These results provide us with a chance to present a method to achieve the minimum size of ETSs of irregular LDPC codes with girth, especially those whose column weight values are a subset of {2, 3, 4, 5, 6} and fulfill the inequality $(b/a)<1$. Moreover, we present a range of numerical results about $(a,b)$ ETSs with girths 8 and 10 to compare the tightness between our proposed lower bounds and the existing bounds in the literature. [ABSTRACT FROM AUTHOR]