algorithm - 最大二分图 (1,n) "matching"

Question

我有一个二分图。我正在寻找最大 (1,n) 个“匹配”，这意味着来自分区 A 的每个顶点都有来自分区 B 的 n 个关联顶点。

下图展示了一个图中的最大(1,3)匹配。为匹配选择的边是红色的，未选择的边是黑色的。

See figure http://www.freeimagehosting.net/uploads/9a8df2d97c.gif

这不同于标准的二分匹配问题，在标准二分匹配问题中，每个顶点仅与一个其他顶点相关联，这可以称为与此表示法匹配的 (1,1)。

如果匹配基数 (n) 不是强制的，而是一个上限(来自 A 的顶点可以有 0 < x <= n 个来自 B 的关联顶点)，那么可以通过将图转换为 a 轻松找到最大匹配流网络并找到最大流。然而，这并不能保证来自 A 的最大数量的顶点将与来自 B 的 n 个关联对。

Answer 1

这是 NP-hard，最大独立集问题的归约。对于任何图 G，您都可以(在多项式时间内)构建问题的一个实例，这样:

• A中的顶点代表G
的顶点
• A的每个顶点恰好连接到B的n个顶点
• A 的任意两个顶点在 B 中有一个公共(public)邻居当且仅当它们在 G 中相连。为了使这始终可行，请选择 n=Δ(G)。

现在实例中的最大“匹配”映射回 G 中的最大独立集。