Bipartite Graph Partitioning (special case)

In the course of my research, I came across a graph matching problem for bipartite graphs, and I am wondering if this particular problem has appeared in the literature before. I suspect it is NP-complete.

The problem assumes a bipartite graph with $N_1$ nodes in the first partition, and $N_2$ nodes in the second, with both $N_{1,2}$ even. Each node is then assigned to one of two clusters, $A$, or $B$, with the restriction that both clusters contain precisely half the nodes for each partition, $N_1/2$ and $N_2/2$. The problem is then to find the cluster assignment that minimizes the number of edges between nodes in different clusters, i.e. the number of times the A/B partitioning cuts the graph edges.

A potential source of confusion here is that there are 2 notions of partitions. The first notion is intrinsic to the original bipartite graph -- there are two sets of vertices, and there are no edges within a set. The second notion is the partitioning asked for by the problem. To avoid confusion I have called this second notion clustering.

• What is your question? You haven't actually asked anything. Feb 6 '18 at 0:24
• I am wondering if this particular problem has appeared in the literature before Feb 6 '18 at 0:45
• Can you formalize the problem in question ? Feb 19 '18 at 14:06

Given bipartite graph $G=(V,E)$ and $K\leq \vert V \vert$ are there two disjoint sets $V_{1}, V_{2}\subseteq V$ such that $\vert V_{1} \vert = \vert V_{2} \vert = K$ and $u\in V_{1}, v\in V_{2}$ implies $(u,v)\in E$