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

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。

形式化地证明这个问题与图论中的任何其他著名问题的等价性也将是有价值的。

谢谢！

注意1：此问题基于带有定向边的最大加权二分匹配，但额外放宽了匹配中的边允许共享起点或终点。由于这种放松会产生很大的差异，因此我创建了一个独立的问题。 注意2：这是一个最大权重匹配。正确结果与匹配中存在多少条边以及被匹配覆盖的顶点数量无关。只有最大权重才有意义。 注意3：在解决问题的过程中，我发现了这篇论文，我认为对于其他试图找到解决方案的人会很有帮助：Alternating cycles and paths in edge-coloured multigraphs: a survey。

注意3：如果有帮助的话，您也可以将该图视为其等价的二边彩色无向多重图。问题的表述将变为：找到没有颜色交替路径或循环的边集，使其权重和最大。

注意4：我怀疑这个问题可能是NP难的，但我对约简不是很有经验，所以我还没有证明它。

另一个例子：

想象一下您有

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也可以。

- fons

---

是只有我一个人这样认为，还是这个定义允许我们将左侧的每个节点连接到右侧的每个节点，并且仍然被称为“方向匹配”？ - K. Bulatov

@cyon 真的！是我的错，你看到了吗？我真的需要一个算法 :) 我已经相应地纠正了问题。 - fons

@Gilles，对于我的跨贴（我是StackExchange的新手）感到抱歉，这个问题已经在CSTheory中关闭了。 - fons

@Yash 非正式地说，我是指只有指向相反方向的边才能在匹配中共享公共顶点。 - fons

@TylerDurden 承认例子可能不够好，但我认为方向匹配的定义足够描述性，不会留下任何问题。你只需要找到权重最高的方向匹配。方向确实很重要，这是解决问题的关键。想象一下，你有4个顶点{u1，u2} {v1，v2}和4条边{u1->v1，u1->v2，u2->v1，v2->u2}。u1->v2和v2->u2不能在同一个方向映射中，v2->u2和u2->v1也不能，但是u1->v1和u1->v2可以，u2->v1也可以。 - fons

Answer 1

按照以下方式定义一个新的无向图G'，该图与G相关：

1. G' 对于G中的每条有向边 (A, B) ，都会创建一个节点(A, B)，带有权重w
2. G' 有一个无向边((A, B),(B, C))，如果在G 中(A, B)和(B, C)均为有向边。

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

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

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

编辑：当所有边权相同时，此后的内容才适用-当边权具有不同值时，这是一个更难的问题（可以使用“最大权重独立顶点集”进行可能的算法搜索）

通常，这将是一个NP难题。但是，G'是一个二分图——它只包含偶数个循环。在二分图中找到最大(加权)独立顶点集不是NP难题。

您将在G'上运行以下算法：

1. 查找G'的连通分量，称为H_1, H_2,...,H_k

对于每个H_i，对节点进行双色着色（红和蓝）。这里的常规方法是在H_i上进行深度优先搜索，交替使用颜色。一种简单的方法是根据G中对应边的方向（从U到V为红，从V到U为蓝）对H_i中的每个顶点进行着色。

从H_i中选择节点的两个选项是选择所有红色节点或所有蓝色节点。选择具有更高权重的着色节点集。例如，红色节点集的权重等于H_i.nodes.where(node => node.color == red).sum(node => node.w)。将更高权重的节点集称为N_i。

您的最大加权独立顶点集现在是union(N_1, N_2, ..., N_k)。

由于G'中的每个顶点都对应于G中的一个有向边，因此您已经得到了最大定向匹配。

- Timothy Shields

---

哇，只需使用线图来建模问题就可以了。Skiena再次正确：设计图而不是算法!!! 我还没有检查整个解决方案（这里已经很晚了），但我会在明天第一时间检查它（看起来你将获得赏金 :))。 - fons

是的，你在那本书中提到的部分总结了我在这个答案中所做的事情：（1）转换图形，（2）应用已知算法（稍作修改）。让我知道它对你有什么帮助。 - Timothy Shields

对于第二步，由于G'是二分图，着色不是很直接吗？只需使用蓝色（红色）表示从U到V的边创建的节点，使用红色（蓝色）表示从V到U创建的节点。我不明白为什么需要深度优先搜索。 - fons

我有一个例子，我不明白这个例子如何解决：U={A,C,E} V={B,D} 和 E={(A->B,10), (B->C,1), (C->D,1), (D->E,10)}。我期望的最大值是20，但使用2-着色却只有11？ - viblo

@viblo 在我的例子中，将图形转换为G'后，N为：{(s->(A,E),7), (s->(B,D),1), (s->(C,E),3), ((A,E)->(F,A),infinite), ((F,A)->t,9)} 最大流量为7，最大加权独立集的总权重为（7+1+3+9）-7 = 13。集合中的顶点是仍然可访问的顶点（其流量<权重），即：(B,D) 的流量为0，权重为1，(C,E) 的流量为0，权重为3，以及 (F,A) 的流量为7，权重为9。 - fons

Answer 2

这个问题可以使用匈牙利算法在多项式时间内解决。Vor上面的“证明”是错误的。

上述示例中解决问题的方法如下：

   D E F
A  # 7 9  
B  1 # #
C  # 3 #

其中"#"表示负无穷。然后使用匈牙利算法解决矩阵，以确定最大匹配。如果要找到最小匹配，可以将数字乘以-1。

- Tyler Durden

---

你如何将匈牙利算法应用于这种情况，其中包括：1）有向边，以及2）解决方案中的边可以共享顶点的可能性？ - mhum

边缘是有方向的这一事实并不重要。如果一个顶点连接到多个顶点，则会产生多个可能的加权结果。例如，在我上面的示例中，A有两个加权值，但B和C只有一个。你也可以在每个顶点之间建立边缘，这将导致一个没有“#”值的完整矩阵。 - Tyler Durden

这完全正确。这不是二分匹配。提问者明确表示他们正在寻找一种被称为“定向匹配”的东西（不是标准术语），在问题中已经定义。图本身被定义为二分图，但据我所知，请求的解决方案并不是二分匹配。 - mhum

好的，在这种情况下，我猜你的意思是{E->A,F->A}被视为一个单一的“单向匹配”，其值为16。然而，这仍然是不可能的，因为如果你进行这样的匹配，那么如何将B/C仅与D匹配呢？目标并不是很清楚，如果不是一对一的匹配的话。我的意思是，如果你允许任何所谓的“匹配”，为什么不匹配所有的东西（这正是你上面的“解决方案”所做的，包括所有4条边）？ - Tyler Durden

是的，在我所述的修改后的情况下，我认为解决方案应该是选择所有边缘。阻止这总是成为解决方案的是这样一个想法：如果A->B和B->C，则不能同时选择A->B和B->C作为解决方案，因为一条边缘的头与另一条边缘的尾相交。这里“匹配”可能是一个不恰当的术语。我认为提问者请求一组有向边缘，使得没有头部重叠任何尾部。 - mhum