二分图划分（特例）：相关文献及NP完全性问询

Great question—this is a really interesting variant of bipartite graph problems that ties together constrained clustering and combinatorial optimization. Let’s break this down:

1. Existing Literature Context #

This problem falls under the umbrella of balanced bipartite biclustering with strict equal-size constraints (or sometimes called equitable bipartite partitioning with dual cluster balance).

From what I’ve worked with in the field, related research exists in several areas:

• Combinatorial Optimization: Many papers on equitable graph partitioning extend their analysis to bipartite graphs, specifically when each partition’s sub-clusters must be exactly half the size of the parent partition. These often frame the problem as a constrained version of minimum cut or maximum matching, with the size constraints added as hard constraints.
• Machine Learning for Graphs: Biclustering of bipartite graphs is a common task in recommendation systems or bioinformatics, but the strict equal-size constraint makes your variant a more specialized case. Some work on "balanced co-clustering" addresses similar size requirements, though not always the exact 50/50 split per partition.
• Operations Research: This problem is sometimes studied as a variant of the quadratic assignment problem (QAP), where the objective (if you’re optimizing for edge cuts or within-cluster edges) maps to QAP’s cost function, with the size constraints as linear constraints.

To dig deeper, search terms like balanced bipartite biclustering equal cluster size, equitable bipartite graph partitioning, or constrained bipartite clustering NP-completeness should lead you to relevant papers.

2. NP-Completeness Verification #

Your hunch that this problem is NP-complete is almost certainly correct, and we can back this up with standard complexity theory reasoning:

• First, the problem is in NP: Given a proposed clustering assignment, you can verify in polynomial time that each partition’s A/B clusters are exactly half the size, and check any additional edge-based objectives (if you have one) quickly.
• Second, we can reduce a known NP-complete problem to this one. For example, take the Partition Problem (given a set of integers, split them into two subsets with equal sum):
  • Construct a bipartite graph where the first partition has $N_1$ nodes (equal to the number of integers, even-sized), and the second partition has $N_2=2k$ nodes (even-sized, k arbitrary).
  • Connect each node in the first partition to k nodes in the second partition if the integer is assigned to subset A, and the other k nodes if assigned to subset B.
  • A valid clustering for your problem (with exactly $N_1/2$ nodes in A/B for the first partition, $N_2/2$ in A/B for the second) directly corresponds to a solution to the Partition Problem. Since Partition is NP-complete, your problem is NP-hard—and thus NP-complete, since it’s in NP.

Additionally, the broader Balanced Graph Partitioning problem (without the bipartite-specific dual constraint) is already NP-complete, so adding more strict constraints only makes the problem no easier.

内容的提问来源于stack exchange，提问作者Surgical Commander