Bipartite Graph Partitioning (special case)

Question

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.

Answer 1

The question does not formalize the problem. However What I understood from the question there is a similar problem known to be NP-complete.

Balanced Complete Bipartite Subgraph Problem

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$

Hope this helps.