dar*_*ios 5 algorithm complexity-theory graph np-hard poset
在尝试分类算法时遇到了以下算法问题.元素被分类为多层次结构,我理解为具有单根的poset.我必须解决以下问题,这看起来很像设置封面问题.
我在这里上传了我的Latex-ed问题描述.
设计满足1和2的近似算法非常简单,只需从G的顶点开始并"向上走"或从根开始并"向下走".假设您从根开始,迭代地展开顶点,然后删除不必要的顶点,直到您至少有k个子格.近似界限取决于顶点的子节点数,这对我的应用程序来说是可以的.
有谁知道这个问题是否有正确的名称,或者问题的树版本？我有兴趣知道这个问题是否是NP难的,也许有人想要一个好的NP难问题来减少或者有一个多项式算法来解决这个问题.如果你们都收取了百万美元的价格.;)
DAG 版本是通过（击鼓）从布景封面上减少来实现的。设置 k = 2 并执行显而易见的操作：条件 (2) 阻止我们求根。（请注意，由于 k 的下界，(3) 实际上并不意味着 (2)。）
树版本是串并偏序集版本的特例，可以在多项式时间内精确求解。这是一个给出多项式 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)。