CODEWITHSUNDEEP
graphcomplexity-theorycombinatoricsdirected-acyclic-graphsposet
Apratim Bhattacharyya
Apratim Bhattacharyya

Reputation: 91

Anti-chain in a partially ordered set (DAG)

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.

Upvotes: 3

Views: 817

Answers (1)

hivert
hivert

Reputation: 10667

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.

Upvotes: 1

Related Questions