我在尝试分类算法时遇到了以下算法问题。元素被分类为多层次结构，我理解为具有单个根的poset。我必须解决以下问题，这看起来很像set cover problem。
我在这里上传了我的乳胶问题描述。
设计一个满足 1 和 2 的近似算法非常容易，只需从 G 的顶点开始并“向上”或从根开始并“向下”。假设您从根开始，迭代地扩展顶点，然后删除不必要的顶点，直到您至少有 k 个子格。近似界取决于顶点的子节点数，这对我的应用程序来说是可以的。
有谁知道这个问题是否有正确的名称，或者问题的树版本？我很想知道这个问题是否是 NP 难的，也许有人对一个好的 NP 难问题有想法来减少或有一个多项式算法来解决这个问题。如果你有两个收集你的百万美元的价格。;)
DAG 版本通过（鼓滚动）从固定覆盖中减少而变硬。设置 k = 2 并做显而易见的事情：条件 (2) 阻止我们生根。（请注意，（3）实际上并不意味着（2），因为下限k。）
树版本是串并行poset版本的一个特例，可以在多项式时间内精确求解。这是一个递归公式，它给出了一个多项式 p(x)，其中 x n的系数是基数 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)。