graph - 偏序集中的反链（DAG）

Question

任何人都可以判断是否存在用于在部分有序集中找到大小为 k 的反链的 P 时间算法？（或 DAG）

我在网上找到的所有资源都涉及找到最大的反链。

Answer 1

我认为这个问题的表述不够精确，因为有两个参数：

• k反链的大小；
• n摆设的大小P；

有一个明确的算法，它是多项式 inn和指数 in k：

• 枚举大小k为 的所有子集P。使用某种格雷码，您可以获得O(1). 因此，成本显然与作为二项式系数的 k 子集的数量成正比choose(n, k)。因此复杂度为O(n^k)。

• 对于每个子集，检查它是否是反链。假设您比较 中的两个元素O(1)。你在O(k^2).

所以愚蠢的算法的复杂度为O(k^2+n^k)，在 中是多项式n。