algorithm - 给定一个双正则图，如何找到一侧具有给定数量顶点的最大边完全二分/双分子图？

Question

例如，我有一个双正则图 G(E,L∪R)。问题是我想找到给定基数 S 或 T 的最大边完全二分子图 K(E',S∪T)。请尽快向我推荐相关文献。

标签： algorithmmathgraphbipartite

Answer 1

派系发现有一个直接的减少，这使得这个 NP 难且难以近似。