algorithm - 二部图中的双重匹配

Question

我在学习算法测试时遇到了以下问题，但没有发布答案:

1. 最大双重匹配问题 - 给定一个二分图 G=(V=(LUR),E) 描述一个算法，该算法返回 E s.t 中的一组边 M 对于 V 中的每个顶点 v 最多有 2 M 中包含最大尺寸 v 的边。

2. 定义:“强双匹配”是对 V 中的每个顶点 v 的双匹配 s.t，M 中至少有一条边包含 v。给定一个二分图 G=(V=(LUR)， E) 和强双重匹配 M，描述了一种返回最大尺寸的强双重匹配 M' 的算法。证明你的答案。

所以我已经设法解决了

1) 使用减少到最大流:将顶点的 s 和 t 以及从 s 到 L 的边和从 R 到 t 的边相加，每个边的容量为 2，并定义 L 和 R 之间每条边的容量为无穷大容量。使用 Dinic 算法找到最大流并返回 L 和 R 之间具有正流的所有边。

关于 2) 我考虑过以某种方式操纵网络，以便每个顶点都有正向流，然后使用某种算法以某种方式构造最大解。有什么想法吗？运行时限制为 O(V^2E)(Dinics 运行时)

Answer 1

这是一个 O(n^3) 的解决方案，使用 minimum cost flow .

回想一下我们是如何为标准二分匹配建立网络的。

1. 对于L中的每个顶点u，添加一条从S到u的单位容量边；
2. 对于每条边u-v，其中u来自L，v来自R，添加一条从 u 到 v 的边。请注意，它的容量并不重要，只要它至少是一个即可；
3. 对于 R 中的每个顶点 v，添加一条从 u 到 R 的单位容量边。

现在我们保持中央部分不变，并稍微改变左右部分。

1. 对于 L 中的每个顶点 u，添加从 S 到 的两条 单位容量边u，其中一个成本为 -1，另一个成本为 0；

同样适用于边 v->S。

忽略成本，这与您自己构建的网络相同。这里的最大流量对应最大双匹配。

现在让我们找出大小为 k 的最小成本流。它对应于一些双重匹配，其中它对应于接触最大可能数量的顶点的匹配，因为接触一个顶点(即，插入至少单位流通过它)会使成本降低 1。此外，接触第二次的顶点不会降低成本，因为第二条边的成本为 0。

我们如何得到解决方案:对于每个 k = 1, ..., 2n 迭代地找到最小成本流并取对应于最小成本的值。

使用 Johnson's algorithm (也称为 Dijkstra's with potentials)每次迭代给出 O(n^2)，总的来说是 O(n^3)。

附言Dinic算法在单位图上的运行时间更好，在二部图上达到O(E sqrt(V))。