12
$\begingroup$

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.

$\endgroup$

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.