"(1:k) Tree-Matching" - 多项式时间内可解决吗？

Question

4

几个月前，有一个不错的问题与“1:n匹配问题”有关，似乎没有多项式时间算法。

我想添加限制条件，使用多项式算法找到1:n匹配问题的最大匹配。我想说：“对于顶点A1，如果顶点未被其他A-顶点占用，则选择{B1、B2、B5}或{B2、B3}中的任意一个。”即我不允许所有可能的组合。

如果我们为每个选择引入辅助顶点H并用树替换边，则可以表达这一点 => 我们得到类似于普通二分图匹配的问题。 A或B的每个顶点只能在匹配中具有一个边缘。来自或到达H顶点的边缘要么全部在匹配中，要么全部不存在于匹配中。想象一下以下三部分图：

alt text

现在定义h_ij="包含H_ij的树"，以便轻松表达匹配：

如果是这样，这个问题是否可以在多项式时间内解决？如果是，是否有带权（w(h_ij))变体的多项式时间解决方案？如果不行，您能否为像我这样的“简单人”提供论据或证明，或建议其他约束条件来解决1：n匹配问题？

例如，这个图可以转换成一个一般图，然后可以使用一般图的加权匹配来解决吗？或者分支甚至匹配森林能帮助到这里吗？

PS：不是作业;-)

- Karussell

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Aryabhatta · Accepted Answer

“maximal”和“maximum”有区别。我假设您在下面的写作中指的是“maximum”。

您似乎没有清楚地定义问题，但如果我正确理解您的意图，那么您的问题似乎是NP完全的（并且“等价于Set Packing”）。

我们可以假设所有A_i的允许集大小相同（k），以找到[1：k]匹配，因为任何其他集大小都可以忽略。要找到最大的k，我们只需为k = 1,2,3等运行[1：k]算法。

所以你的问题是（我想……）：

给定m个集合族F_i = {S_1i，..，S_n（i）i}（|F_i| = F_i的大小= n（i），不需要与|F_j|相同），每个集合的大小为k，您必须从每个家庭中找到一个集合（称为S_i），使得

我们可以通过两个步骤证明k=3时是NP-Complete问题：

将NP-Complete问题Set Packing进行归约，这表明它是NP-Hard问题。
您的问题在NP中，可以被归约到Set Packing问题。这和步骤1）意味着您的问题是NP-Complete问题。这也有助于您利用任何已经存在于Set-Packing问题的近似/随机算法。

Set Packing问题如下：

给定n个集合S_1, S_2, ..., S_n，找出其中最大数量的两两不交的集合。

即使|S_1|=|S_2|=...=|S_n|=3，这个问题仍然是NP-Complete问题，称为3-Set packing问题。

我们将使用此问题来展示您的问题是NP-Hard问题，通过提供从3-Set packing问题到您的问题的简单归约。

只需给出S_1、S_2、...、S_n，形成家族

F_i = {S_i}。

现在，如果你的问题有多项式时间解决方案，那么我们会得到一组不相交的集合{S_1，S_2，...，S_r}，满足以下条件：

- S_i和S_j互不相交 - S_i的数量最大

这个简单的约化给了我们一个3集装箱问题的解决方案，因此你的问题是NP难问题。

为了证明这个问题在NP中，我们将其约化为集合覆盖问题：

给定F_i = {S_1i，S_2i，...，S_ni}

我们考虑集合T_ji = S_ji U {i}（即我们将家族的id添加到集合本身中），并运行它们通过集合覆盖算法。我会让你自己看出为什么集合覆盖问题的解决方案可以解决你的问题。

对于一个最大解，你只需要使用贪心算法。一直选择集合，直到不能再选择为止。这将是多项式时间。