双正则图给定单侧顶点数的最大边完全二部子图求解及文献推荐

你提到的问题属于固定单侧基数的最大边二部团问题的子类，针对输入为双正则二部图的特殊场景，目前主流求解方案可分为以下几类：

核心求解方案 #

• 精确求解（小规模图适用）
  固定单侧顶点基数的约束下，最大边二部团的边数为|S|*|T|，因此问题可等价转化为：找到大小为指定值的单侧顶点子集，使得该子集的公共邻居数量最大。
  对顶点数在万级以下的图，可直接通过枚举+剪枝实现：遍历所有符合基数要求的单侧顶点子集，计算每个子集的公共邻居规模，取最大值对应的子集即可。如果图规模偏大，可以引入分支定界策略，预先按顶点邻居重叠度排序，提前剪掉不可能超过当前最优解的分支，大幅降低遍历复杂度。
• 启发式求解（大规模图适用）
  双正则图的左部顶点度数、右部顶点度数分别相等的结构特性可以被直接利用，采用贪心策略可得到有近似比保证的解：
  1. 初始化候选顶点集为空，每次选择与当前候选集公共邻居最多的顶点加入，直到候选集大小达到约束值
  2. 取候选集的公共邻居作为另一侧顶点集，得到的二部团就是近似最优解
     该方法在双正则图场景下的近似比可达1-1/e，适合十万顶点以上的大规模图场景。
• 特殊结构优化
  如果你的双正则图是半正则（一侧顶点度数为1）、完全二部图等特殊子类，可以直接通过公式推导得到最优解：利用双正则图的对称性，任意符合基数要求的顶点子集的公共邻居规模相等，直接通过度数、总顶点数的计数关系就能算出最大边数。

权威研究文献推荐 #

• Biclique Problems: A Survey：二部团领域的经典综述，完整覆盖了各类二部团问题的复杂度、求解框架、特殊图结构下的优化方案，专门提及了正则/双正则图场景下的问题简化方法，是该领域的入门必读文献。
• Maximum Biclique Problems in Bipartite Graphs: A Computational Study：该文针对不同约束下的二部团问题做了系统的算法对比实验，包含固定单侧基数的场景，给出了不同规模、不同结构图下的最优算法选型建议，也提供了双正则图测试集上的性能基准数据。
• Exact and heuristic algorithms for the maximum edge biclique problem：针对最大边二部团问题的专门研究，提出了约束场景下的高性能分支定界精确算法和启发式算法，文中给出的算法框架可以直接适配双正则图的特性做优化。

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