algorithm - 允许共享开始/结束顶点的有向最大加权二分匹配

Question

令 G (U u V, E) 为带权有向二分图(即 U 和 V 是二分图的两组节点，E 包含从 U 到 V 或从 V 到 U 的有向加权边)。这是一个例子:

在这种情况下:

U = {A,B,C} 
V = {D,E,F} 
E = {(A->E,7), (B->D,1), (C->E,3), (F->A,9)} 

定义: DirectionalMatching(我编造这个术语只是为了让事情更清楚):一组可以共享起始或结束顶点的有向边。也就是说，如果 U->V 和 U'->V' 都属于 DirectionalMatching，则 V/= U' 和 V'/= U 但也可能是 U = U' 或 V = V'。

我的问题:如何有效地找到一个 DirectionalMatching，如上定义，用于最大化其边缘权重总和的二分方向加权图？

高效，我的意思是多项式复杂度或更快，我已经知道如何实现朴素的蛮力方法。

在上面的示例中，最大加权 DirectionalMatching 是:{F->A,C->E,B->D}，值为 13。

正式证明此问题与图论中任何其他众所周知的问题的等价性也很有值(value)。

谢谢!

注1:本题基于Maximum weighted bipartite matching _with_ directed edges但额外的放松是允许匹配中的边共享起点或终点。由于这种放松会产生很大的不同，因此我创建了一个独立的问题。

注2:这是最大权重匹配。基数(存在多少条边)和匹配覆盖的顶点数与正确结果无关。只有最大重量很重要。

注意 2: 在我研究解决问题的过程中，我发现了这篇论文，我认为它会对其他试图找到解决方案的人有所帮助:Alternating cycles and paths in edge-coloured multigraphs: a survey

注意 3: 如果有帮助，您还可以将该图视为其等效的 2 边彩色无向二分图。然后，问题公式将变成:找到一组没有颜色交替路径或循环的具有最大权重和的边。

注意 4:我怀疑这个问题可能是 NP-hard，但我对归约没有那么多经验，所以我还没有设法证明这一点。

又一个例子:

想象一下

4 个顶点:{u1, u2} {v1, v2}

4 条边:{u1->v1, u1->v2, u2->v1, v2->u2}

然后，不管它们的重量如何，u1->v2和 v2->u2不能在同一个 DirectionalMatching 中，v2->u2 也不能和 u2->v1 .然而u1->v1和 u1->v2可以，也可以u1->v1和 u2->v1 .

Answer 1

定义一个新的无向图G'来自 G如下。

1. G'有一个节点 (A, B)有重量w对于每条有向边 (A, B)有重量w在G
2. G'有无向边((A, B),(B, C))如果 (A, B) 和 (B, C) 都是 G 中的有向边

http://en.wikipedia.org/wiki/Line_graph#Line_digraphs

现在在 G' 中找到一个最大(加权)独立顶点集.

http://en.wikipedia.org/wiki/Vertex_independent_set

编辑:这一点之后的东西只有在所有边权重都相同时才有效——当边权重具有不同的值时，这是一个更困难的问题(谷歌“最大权重独立顶点集”可能的算法)

通常这是一个 NP-hard 问题。然而，G'是一个二部图——它只包含偶数圈。在二分图中寻找最大(加权)独立顶点集不是 NP-hard。

您将在 G' 上运行的算法如下。

1. 找到 G' 的连通分量，说 H_1, H_2, ..., H_k
2. 对于每个 H_i对节点进行二次着色(比如红色和蓝色)。这里的食谱方法是对 H_i 进行深度优先搜索。交替的颜色。一种简单的方法是为 H_i 中的每个顶点着色。根据G中是否对应边来自 U至 V (红色)或来自 V至 U (蓝色)。
3. 从H_i中选择节点的两个选项是所有红色节点或所有蓝色节点。选择具有较高权重的彩色节点集。例如，红色节点集的权重等于 H_i.nodes.where(node => node.color == red).sum(node => node.w) .调用更高权重的节点集N_i .
4. 您的最大加权独立顶点集现在是 union(N_1, N_2, ..., N_k) .

由于 G' 中的每个顶点对应于 G 中的一个有向边，你有最大的 DirectionalMatching。