4
$\begingroup$

Given a set $S$ with strict partial order $<$. Let $A\subseteq S$ be a downward-closed subset of $S$ (in other words, if $a<b$ and $b\in A$, then $a\in A$). How many subsets of $S$ are downward-closed?

Are there algorithms that can solve the problem in time polynomial in $|S|$?

$\endgroup$
2
  • 1
    $\begingroup$ Is there any particular reason for using $<$ instead of $\leq$? $\endgroup$ Nov 6 '11 at 4:23
  • $\begingroup$ strict order make sure the graph is for the order is a DAG. $\endgroup$
    – Chao Xu
    Nov 6 '11 at 4:27
8
$\begingroup$

See three closely related questions Does faster exact algorithm for counting independent sets in comparability graphs than general graph exisits? and Is counting maximal cliques in an incomparability graph #P-complete? and https://mathoverflow.net/questions/49515/on-the-number-of-antichains-of-a-poset

They are all on antichains rather than downward-closed sets but downward-closed sets correspond one-for-one with the antichains of their maximal elements.

I believe both of the cstheory questions have answers with references that also answer your question: no, the problem is #P-complete.

$\endgroup$
6
$\begingroup$

An additional comment: in case your partially ordered set is the power set of a given set (e.g., [n]) ordered by the inclusion, more is known when n is small. Specifically see the Dedekind numbers article and the Sloane integer sequence. The asymptotic behavior has been studied also. Hansel in 1966 proved that the number of antichains of subsets of an n-set is upper-bounded by $3^{{n \choose \lfloor n/2\rfloor}}$. Later, Kleitman and Markowsky improved this bound. For further results see the references in this Wikipedia article. Finally, another reference (in addition to the Provan-Ball paper which appears in one of the links above) of interest to you probably is "On the relative complexity of approximate counting problems", by Dyer, Goldberg, Greenhill and Jerrum.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.