graph - 部分有序集中的反链 (DAG)

Question

谁能告诉我是否存在 P 时间算法来在偏序集合中找到大小为 k 的反链？ (或 DAG)

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

Answer 1

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

• k 反链的大小；
• n 偏序集P的大小；

有一个明确的算法，它是 n 中的多项式和 k 中的指数:

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

• 对于每个子集，检查它是否是反链。假设您在 O(1) 中比较偏序集的两个元素。您在 O(k^2) 中执行此操作。

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