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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.