允许共享起始/结束顶点的定向最大加权二分匹配

令 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)} 

定义： 定向匹配（我创造这个术语只是为了让事情更清楚）：可能共享起始或结束顶点的有向边集。也就是说，如果 U->V 和 U'->V' 都属于定向匹配那么 V /= U' 且 V' /= U 但也可能是 U = U' 或 V = V'。

我的问题：如何高效寻找定向匹配，如上所定义，对于二部有向加权图，其边的权重之和最大化？

By 有效率的，我的意思是多项式复杂性或更快，我已经知道如何实现朴素的暴力方法。

在上面的例子中，最大权重定向匹配是：{F->A,C->E,B->D}，值为 13。

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

Thanks!

Note 1:这个问题是基于与有向边的最大加权二分匹配 https://stackoverflow.com/questions/14824320/maximum-weighted-bipartite-matching-with-directed-edges但更加宽松的是，允许匹配中的边共享起点或目的地。由于放松会产生很大的影响，因此我创建了一个独立的问题。

Note 2:这是一个最大值weight匹配。基数（存在多少条边）和匹配覆盖的顶点数量与正确结果无关。只有最大重量才重要。

Note 2:在我研究解决问题的过程中，我发现了这篇论文，我认为这对其他试图找到解决方案的人会有所帮助：边缘颜色的交替循环和路径 多重图：一项调查 http://www.cs.rhul.ac.uk/~gutin/paperstsp/alt.pdf

Note 3:如果有帮助的话，您还可以将该图视为其等效的 2 边彩色无向二分多重图。那么问题的表述将变成：找到没有颜色交替路径或循环且权重总和最大的边集。

Note 4:我怀疑这个问题可能是 NP 难问题，但我在缩减方面没有那么丰富的经验，所以我还没有设法证明这一点。

另一个例子:

想象一下你有

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

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

然后，无论他们的体重如何，u1->v2 and v2->u2不能在同一个定向匹配, 也不能v2->u2 and u2->v1。然而u1->v1 and u1->v2可以，也可以u1->v1 and u2->v1.

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

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

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

现在找到一个最大（加权）独立顶点集G'.

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

编辑：此后的内容仅在所有边权重相同时才有效 - 当边权重具有不同值时，这是一个更困难的问题（谷歌“最大权重独立顶点集”以获取可能的算法）

通常这将是一个 NP 难题。然而，G'是一个二分图——它只包含偶数环。查找二分图中的最大（加权）独立顶点集是notNP-困难。

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

1. 找到以下的连通分量G', say H_1, H_2, ..., H_k
2. 对于每个H_i对节点进行 2 种着色（例如红色和蓝色）。这里的食谱方法是进行深度优先搜索H_i交替颜色。一个简单的方法是将每个顶点着色H_i基于是否对应的边G来自U to V（红色）或来自V to U (blue).
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。