cryptography etc. This paper gives a bijection between two classes of lattice path s× in agnrid. This bijection is crucial for identifying short cycles in simple bipartite graphs. We also give an algorithm for generating such paths with the complexity o f ( 41/2 ). The proposed work lays the groundwork for counting cycles of leng thtfor2o−m2 in bipartite graphs, whereis the girth of the graph. which has broader implications on Error correcting codes, The author(s) have not employed any Generative AI tools. The computational challenge of counting cycles in graph structures represents a persistent research frontier, particularly given its #P-complete problem. This complexity has driven specialized investigations into graph classes with practical applications. Among these, bipartite graphs hold significant importance due to their role in communication systems, where they form Tanner graphs for error-correcting codes like LDPC codes [1, 2]. There are works in counting short cycles in a bipartite g3,r4a,p5h, 6[].
We map these patterns as lattice paths i n×t hegrid. The set of all integer vectors i n-the dimensional space can be written ℤas: = {( 1, 2, … , ) | ∈ ℤ}. A lattice path in ℤ of length is a sequence( 0, 1, … , ), where ∈ ℤ , such that each consecutive diference− −1 lies in , where is the set of step vector7]s. [ ( → ; |) follows a defined restricti onwhile taking steps that belong [t8o].
represents the set of all lattice paths fro m tpointthat CEUR
ceur-ws.org we omit from the notation o. fThe set of such paths subject to given restrictiiosndsenoted by 2 ( → ∣ ) .
In this section, we define special lattice paths motivated by the patterns descr3i]b.eTdhine m[otivation for such patterns is that some are impossible in the modified BFS tree. We deno tℎeltehvel of this modified BFS tree by . For example, in Figure5, the two vertice0s and 1 at level2 −3 have a length path2 − 3 from the source. Thus, the cycl e− 0 − 1 − has length2(2 − 3) + 2 = − 4 < , which contradicts the girth condition. Therefore, the path is invalid.
This translates to a restriction wReigchatl-lThen-Up: a path cannot go down and then up above the line (see Figure5). Since our work rotates this grid (see Fig3)u,roeur path cannot go “Right-Then-Up” 2 above the line= . We will define this formally in Definitio3n.
Definition 1 (Lattice Path.s)We use the notation ( → ∣ ) to denote all lattice paths from point to point with restrictions . If the starting point , the ending point , and the length are not explicitly provided, they are assumed to be (0, 0), (, ) , and = 2 , respectively.
() = 2 ((0, 0) → (, ) ∣ ) Definition 2 ( + 2 Constrained Path. sA)n + 2 constrained path, as illustrated in Figure 6, is a lattice path such that + 2 ≥ for all points = ( , )along the path. This constraint ensures that the path stays on or below the line = + 2 throughout its traversal. The set of all such paths is denoted by: ℙ = ( + 2 ≥ ∀ ∈ {0, 1, … , 2}) Definition 3 (Right-Then-Up Constrained Pat.hFso)r every consecutive pair of steps, if the step from −1 to is a right step (1, 0), and = ( , )satisfies ≥ + 1, then the next step from to +1 must also be a right step (1, 0). The set of Right-Then-Up Constrained Paths is denoted by: ℍ = ( − −1 = (1, 0)and ≥ + 1 ⇒ +1 − = (1, 0), ∀ ∈ {1, 2, … , 2 − 1} ) (1)
It can be observed that these paths form a specific “inverted L-shaped” structure above t=he l,ine as illustrated in Figu7rae.
In this section, we show that there exists a bijection betwe+en2 thcoenstrained pathℙs)(and the Right-Then-Up constrained pathℍs).( Before this, we first define a few notations and a supporting lemma. a cycle is invalid or does not exist because there is a vertex located above level /2 that has two connected vertices, which could form a cycle shorter than the girth . This contradiction renders the pattern invalid, refer [3]. Consequently, this condition is used as a constraint for Right-Then-Up Constrained paths.
(4, 4) =
2 + =
2 + (0, 0) by (, ) , where and are the indices of the endpoints: Definition 5.
We define a function ∶ ℍ
→ ℙ such that, for each lattice point in the path = ( 0, 1, … , 2 ) ∈ ℍ, we apply a function :
(, ) = ( , +1 , … , ). ( ) = ( (
0), ( 1), … , ( 2 )), ( ) = { +−1 (⌊ 2 ⌋ , ⌊ ++2 2
if + 2 > , ⌋) if + 2 ≤ . where ∶ ℤ 2 → ℤ2 is defined for a point = ( , )
as
Alternatively, this func tiocann be defined in terms of the index of the point. Sincsetarts a(t0, 0) and consists of only single steps in either direction, we can observe that for a n=y (p o,in )tin , = = we have = + . Thus, we can rewrit eas follows: ( ) ={
if + 2 > , (⌊−1 ⌋ , ⌊+22 ⌋) if + 2 ≤ .
2 onward, we denote as the th point in ∈ ℍ .
We can easily verify tha(t ) lies on or below the lin=e + 2 , thus () ∈ ℙ . From this point
are the same for both1 and 2. 1 and 2 denote theth points in 1 and 2, respectively.
Proof. First, let us prove the injectivity of the fu nc.tLieotn 1, 2 ∈ ℍ such that( 1) = ( 2). Let one of −11 or +11 must lie on the li ne= . Denote such a point b y1.
Consider any point1 ∈ 1 such that it lies on the li=n e+ 1 . If both −11 and +11 lie on the line = + 2 , then we hav e1 − −11 = (1, 0)(i.e., the path moved to the right), a+1n1d − 1 = (0, 1)(i.e., the path moved up). Since = + 1, this contradicts the restrictioℍns. Tohfis implies that at least As 1 lies below the li ne= + 2 , we know that( 1 ) = 1. Since ( 1 ) = ( 2), it follows that 1 = ( 2), which means ( 2)lies on the lin e= . From Lemma 2, we conclude tha t( 2 The last two equations imply th1a=t 2. Therefore ,2 also lies on the lin=e . Now, since 2 is ) = 2. adjacent to2, it must lie below the li n=e + 2 . This implies ( 2) = 2. Given that( 1) = ( 2), and 1 lies on the lin e= + 1 , it follows th a(t1) = 1, hence 1 = 2. Thus, we have shown that Let the indices of points that lie on the=lin+e 1 be 0, 1, 2, … , . Consider the subpaths 1 ( , +1 )and 2 ( , +1 ). To show that1 = 2, it is suficient to prove that ∀ ∈ {0, 1, … , − 1}, 1( , +1 ) = 2 ( , +1 ), along with
This would complete the proof of the injectivi t.y of
We note that the subpaths mentioned above cannot cross or touch t=he+l1ine; they must lie entirely either above or below this line, except at the endpoints. Let us denote one such pair of subpaths as 1(, ) and 2(, ) . We first prove that these subpaths lie on the same side of th e=li+ne1 .
Assume, for the sake of contradiction, th a1t(, ) and 2(, ) lie on opposite sides of the line = + 1 , and without loss of generality, sup p o se1(, ) lies above the line. Then, for all ∈ {, + 1, … , } , we have 1 > 1 + 1 and 2 < 2 + 1. Since 1 ≥ 1 + 2, we use the definition: ( 1) = (⌊ − 1 2 ⌋ , ⌊ + 2 2 ⌋) .
This means ( 1) lies above the lin e= + 1 . On the other hand(, 2) = 2 lies below the line = + 1 , which contradicts the assumption t(h at1) = ( 2). Hence, both subpaths must lie on the same side of the lin e= + 1 . Next, we show that all the points in the corresponding subpat1hs of and 2 coincide.
• First case: Both subpaths lie above the lin=e + 1 . There exists only one unique inverted L-shaped pat h1 from to that satisfies the constraintℍso.fHence,
1(, ) = 2(, ). • Second case: Both subpaths lie below the l i=n e+ 1 . Since ( ) = for points below the line = + 2 , we have: ( 1(, )) = 1(, )
and ( 2(, )) = 2(, ).
Given that( 1) = ( 2), it follows that: ( 1(, )) = (
2(, )) ⟹ 1(, ) = 2(, ).
Now, let us prove the surjectivity of the func.tWioen aim to show that for any pat1h∈ ℙ (a path constrained below the lin=e + 2 ), there exists a pa th2 ∈ ℍ (a Right-Then-Up constrained path) such that( 2) = 1. We will prove this by explicitly constructi2nfgrom 1.
Let 1 be a lattice pathℙi n.Suppose 1, 2, … , are the indices of the points o1nthat lie on the line = + 1 , where the point immediately before lies=o n . Similarly, le t1, 2, … , be the indices of the points o n1 that lie o n= + 1 , where the point immediately after lies o=n . In Figure8a, the first set of indices (t h-evalues) indicates “entry” into the reg≥io n+ 1 (blue lines), while the second set (the-values) indicates “exit” from this region (orange lines).
As the path starts fr(o0m, 0), which lies outside the regio≥n + 1 , it must first enter the region before it can exit. Therefore, the following inequality holds: 0 < 1 ≤ 1 < 2 ≤ 2 < ⋯ < ≤ < 2. (2)
We will refer to the set of corresponding subpaths determined by the indices in the above equation as thezig-zag partition, denoted by , because one can observe zig-zag paths between the li=ne+s 1 and = + 2 , as illustrated in Figu8rae. 1For any subpat h (, ) lying abov e = + 1 , it must make = − right steps an d= − up steps. The restrictions ofℍ do not allow an up step after a right step. Therefore, the subpath must makuepasltleps first, followed by allright steps, forming a unique inverted L-shaped path.
For each subpath o f1 corresponding to the “zig-zag partition,” we construct the corresponding subpath o f 2. After the construction, to prove t h(at2) = 1, it will be suficient to show that for all subpaths 1(, ) ∈ , we have
This will establish t haits surjective. We observe that, due to the way we defined the partition, each subpath is either entirely on or above the=lin+e1 (i.e., inside the region≥ + 1 ), or entirely on or below the li ne= + 1 (i.e., outside the regio n≥ + 1 ).
We will construct the subpaths 2ofusing the following two cases.
• First case: For subpaths below the li n=e +1 in the “zig-zag partition,” we retain these subpaths in 2 as they are. That is, for a ll1(, ) ∈ that lie below= + 1 , we set
2(, ) = 1(, ).
Since the subpath 2(, ) lies entirely belo w= + 1 , it follows from the definition otfhat • Second case: For each subpath 1(, ) ∈ that lies on or above the l=ine+1 , the endpoints will always be on the l in=e + 1 . In this case, we construct a “reverse L-shaped” subpath in 2, as shown in Figure8b in teal. Specifically, 2(, ) is given by: 2(, ) = ( +21 , −21 ) , ( +21 , −21 + 1) , … , ( +21 , −21 ) , ( +21 + 1, −21 ) , … , ( +21 , −21 ) . This subpath lies entirely above the l=ine+ 1 and forms a valid Right-Then-Up path, as required by the constraintsℍo.f We now verify tha (t 2(, )) = 1(, ) for such subpaths. Note that for any p ooinnt or above the lin e= + 1 , the image () also lies on or above the li=ne + 1 . Thus, both ( 2(, )) and 1(, ) lie entirely abo ve= + 1 .
However, since both must also lie below or on th e=lin+e2 , and because there is a unique subpath between two endpoin tsand such that all intermediate points s a+t1is≤fy ≤ +2 2, we conclude that
( 2(, )) = 1(, ).
For any pat h 1 ∈ ℙ, we have explicitly constructed a pat2h∈ ℍ such that( 2) = 1. Thus, is surjective.
In the previous section, we established a bijection bet w+e2enconstrained paths andRight-Then-Up constrained paths. Thus, to compute the cardinality of Right-Then-Up constrained paths, it sufices to determine the cardinalit y+of2 constrained paths.
We apply a coordinate transformation f(r, o)m to a new coordinate syste(m′, ′)such that: Under this transformation, the number of paths ′ = + 2
and ′ = . | 2 ((0, 0) → (, ) | + 2 ≥ , ∀ ∈ {0, 1, … , 2} )| | 2 ((2, 0) → ( + 2, ) | ′ ≥ ′, ∀ ∈ {0, 1, … , 2} )|. is equivalent to
We will use the following theorem for counting such paths: 2If a point lies on= + 1 , then the next step must be an up-step; if a point lie=s o+n2 , then the next step must be a right-step. This enforces a unique “zig-zag” structure. below the line = is given by: | ((, ) → (, ) ∣ ≥ )| = ( + − − − ) − ( + − − − + 1 ).
Applying this theorem to
| 2 ( 0 → 2 | ≥ , ∀ ∈ {0, 1, … , 2}) | , with 0 = (2, 0)and 2 = ( + 2, ) , we obtain: |ℙ| = |ℍ| = | ((2, 0) → ( + 2, ) ∣ ≥ )| = ( ) − (
(3) 2
2
In this section we will propose an algorithm to generate Right-Then-Up constrained p×a thgirnida.n The core idea of the algorithm is to generate paths that are entir e=l y+be2lowand then apply the construction mentioned in the surjuctive proof above. The1owreilml ensure that we will generate all paths with one-to-one correspondence. Algor4itghemnerates paths that are be l=o w+ 2 . While Algorithm3 using Algorithm1,2 transform those pathsRtigoht-Then-Up constrained paths.
Algorithm1 computes thezigzag partition of a given path by identifying specific points within the input path that satisfy the condition mentioned for indices in E2q.uIaftaioponint satisfies these criteria, its index is added to an arrapyartitionPoints, which contains the indices of all partition points. These points divide the path into distinct segments represented by i n1d≤ice1s < 2 ≤ 2 < ⋯ < ≤ , where[ , ] denotes the boundaries of the partitions. The path within each alternate interval exhibits a zigzag structure, hence the tzeirgmzag partitions. Algorithm2 transforms each “zigzag partition“ into an inverted -shape, as shown in Figur8eb
Algorithm4 is an recursive algorithm that takes three incuprurtPsa:th, the path traversed so far; Paths, a collection of all generated paths; ,atnhde grid size. It checks the position of last point in currPath and terminates the branch if it is outside the grid, if the point reaches the destination, currPath is appended toPaths, and then the branch terminates. Otherwise, the algorithm branches to two potential moves: a right step or an upward step , provided the new point lies on or below the line = + 2 . For each valid move, a copy ocfurrPath is created, the new point is appended, and the function is called recursively with the updated path. This process ensures that+a2ll cvoanlsitdrained paths are generated and storedPianths. To convert these pathsRtioght-Then-Up constrained paths, we call the Algorith3mfor each path iPnaths. The total number o+f 2 constrained path, |ℙ|, is given by
The cost of generating a single pa t(h)is. Thus, the overall time complexity for generating all paths is Since the transformation of each path (Algo3r)itahlsmo requires() time, the overall complexity for generatingRight-Then-Up constrained paths remains |ℙ| = ( ) − (
). 2 |ℙ| ∼
2
can be accomplished with an overall computational complex it(y 4 In this paper, we introduced an algorithm to generate a class of special lattice paths w i×thi,n a grid which is particularly useful to identify and analyze short cycles in undirected bipartite graphs. A central contribution of this work is to establish a bijection be+tw2eecnonstrained paths andRight-Then-Up constrained paths. We demonstrated that the generation and transformation processes for these paths o1/f2 ). These paths are equivalent to patterns that are used to find cycles in bipartite gr3a].phTshi[s work can be used to extend the algorithm to find short cycles over a wider range of lengths. This study establishes a solid foundation for further exploration of lattice path transformations and their utility in solving complex combinatoria problems. 21–28. doi:10.1109/TIT.1962.1057683.
Theory 27 (1981) 533–547. doi1: 0.1109/TIT.1981.1056404. [1] R. Gallager, Low-density parity-check codes, IRE Transactions on Information Theory 8 (1962) [2] R. Tanner, A recursive approach to low complexity codes, IEEE Transactions on Information [3] A. Dehghan, A. H. Banihashemi, Counting short cycles in bipartite graphs: A fast technique/algorithm and a hardness result, IEEE Transactions on Communications 68 (2020) 1378–1390. URL: https://doi.org/10.1109/TCOMM.2019.296239. 7 [4] M. Karimi, A. H. Banihashemi, Message-passing algorithms for counting short cycles in a graph, IEEE
Transactions on Communications 61 (2013) 485–495. d1o0i.:1109/TCOMM.2012.100912.120503. [5] J. Li, S. Lin, K. Abdel-Ghafar, Improved message-passing algorithm for counting short cycles in bipartite graphs, in: 2015 IEEE International Symposium on Information Theory (ISIT), 2015, pp. 416–420. doi:10.1109/ISIT.2015.7282488. [6] I. F. Blake, S. Lin, On short cycle enumeration in biregular bipartite graphs, IEEE Transactions on