选择 k 个子偏序集

Question

我在尝试分类算法时遇到了以下算法问题。元素被归类为一个多层级结构，我理解它是带有单个根的偏序集。我必须解决以下问题，它看起来很像集合覆盖问题。

我在这里上传了我的LaTeX问题描述（链接）。

设计一个满足1和2的近似算法非常容易，只需从G的顶点“向上”或从根开始“向下”进行。假设您从根开始，迭代地扩展顶点，然后删除不必要的顶点，直到您至少拥有k个子格。逼近界限取决于顶点的子节点数量，对于我的应用程序来说这是可以接受的。

有人知道这个问题是否有一个适当的名称，或者可能是树版本的问题吗？我想知道这个问题是否是NP难的，也许有人有好的NP难问题来减少或者有多项式算法来解决这个问题。如果你两者都有，就可以获得百万美元的奖金。;)

- dareios

---

我不明白。如果您选择S' = {r}，其中r是根节点，则\sigma(r) = V。您的意思是sigma(s)是所有小于或等于r且大于或等于s的元素（其中小于和大于是格子偏序）吗？ - deinst

@deinst 这就是为什么要有 k：为了使问题更加有趣 :) 当 k=1 时，解决方案为 S={r}。 - Bolo

@dareios 你可能需要在问题陈述中纠正两个小错误。1）倒数第二段通常不是正确的，这取决于 G 的选择（除非我有遗漏，如果 G 包含两个子节点且没有更多内容，则具有 l = k = 2 的解 S = G 是一个解）。2）在倒数第三段中，你可能想表达的是：“[...] 我们仍然希望保留 2。” - Bolo

更准确地说，您是否具有二进制的交集和/或连接？ - user382751

@Bolo 所以属性3应说明不存在S'，使得k <= |S'| < l。 - deinst

Answer 1

DAG版本是通过从集合覆盖中的一个缩减得到的。设置k = 2并执行明显的操作：条件（2）防止我们取根。请注意，由于下限k，（3）实际上并不意味着（2）。

树版本是序列并偏序版本的特例，可以在多项式时间内精确解决。这里有一个递归公式，给出一个多项式p(x)，其中x的系数为n的覆盖数。

要覆盖的单个顶点：p(x) = x。

其他顶点：p(x) = 1 + x。

并行组合，其中q和r是两个偏序的多项式：q(x)r(x)。

系列组合，其中q是顶部偏序的多项式，r是底部的多项式：如果顶部偏序不包含需要覆盖的顶点，则p(x) = (q(x) - 1) + r(x)；否则，p(x) = q(x)。

- user382751

---

好的观察，(3)并不意味着(2)，我完全忽略了这一点。问题陈述已经更改。至于其他部分，我想我需要先休息一晚，谢谢你的回答！ - dareios

简化确实很容易，不知道昨天为什么做不到。谢谢！ - dareios

对于树形递归公式：如果我只有一个顶点需要覆盖，那么我有p(x)=x，因为只有一个覆盖。如果没有顶点需要被覆盖，我们应该有p(x)=1（因为空覆盖）。我不明白何时应用“其他顶点：p(x)=1+x”多项式。此外，我不明白何时应用“最上面的偏序不包含顶点”（需要被覆盖）：最上面的偏序将始终包含其他偏序，因此如果它不包含需要被覆盖的顶点，则其他偏序也不会包含。也许这里涉及到最小属性的>= k限制？ - dareios

这是1 + x，因为您没有要求覆盖中的每个顶点实际上都要覆盖任何内容，因此您可以选择是否包含它。如果必须覆盖（子）树根，则必须将其放入并将其所有适当的后代留出。 - user382751