A directed complete bipartite graph is a bipartite graph where there is exactly one directed edge between any two vertices from its two different parts. In other words, it's an orientation of a complete bipartite graph.
Given a directed complete bipartite graph, we are asked to find the largest set of edge-disjoint 4-cycles. Note that these 4-cycles can share node(s).
Is this problem NP-Hard? I tried to reduce from 2P2N-3SAT to this problem, but failed. On the other hand, I found no polynomial algorithm could solve it optimally.
