Finding the longest cycle in a bipartite graph?

Question

Given an undirected unweighted and unbalanced bipartite graph, I am looking for an algorithm (and maybe an implementation?), to find (approximately?) longest simple cycles. In my problem each part contains thousands of nodes.

Answer 1

This problem is NP-hard via a reduction from the Hamiltonian path problem. Given a graph $G$, form a new graph $G’$ by taking each edge $\{u, v\}$ and splitting it into a series of two edges $\{u, x_{uv}\}$ and $\{x_{uv}, v\}$, where $x_{uv}$ is a new node. (Essentially, this places a new node in the middle of each existing edge.) You can prove that this new graph is always bipartite (the original nodes and new nodes form the two bipartite classes) and that there’s a path from a node $u$ to a node $v$ in $G$ if and only if there’s a path from $u$ to $v$ in $G’$ (either insert the appropriate $x_{uv}$ nodes between each pair of nodes in the original path or delete them). Therefore, finding cycles in $G$ is essentially equivalent to finding cycles in $G’$, so finding large cycles in $G’$ gives a way to find large cycles in $G$.

This reduction not only shows that the problem of finding large cycles in a bipartite graph is hard, but that it’s more or less equivalent to finding them in general graphs. As a result, you may want to just search for algorithms for finding long cycles in general graphs.