Anti-chain in a partially ordered set (DAG)

Question

Can anyone tell if there exists a P-time algorithm for finding a anti-chain of size k in a partially ordered set? (or a DAG)

All resources I found online deal with finding the maximum anti-chain.

Answer 1

I think the formulation of the question is not precise enough since there are two parameters:

• k the size of the antichain;
• n the size of the poset P;

There is a clear algorithm which is polynomial in n and exponential in k:

• enumerate all the subsets of size k of P. Using some kind of gray code you can get each subset in O(1). So the cost is clearly proportional to the number of k-subsets which is a binomial coefficient choose(n, k). The complexity is therefore O(n^k).

• for each subsets, check if it's an antichain. Assuming you compare two elements of the poset in O(1). You do that in O(k^2).

So the stupid algorithm as a complexity of O(k^2+n^k), which is polynomial in n.