3
$\begingroup$

This post is a little lengthy, thank your for your patience for reading. ^_^

As known, counting antichains in a poset is #P-complete, so it is NP-hard to get the exact answer. Following is my simple divide-conquer algorithm for the antichain counting problem (#ANTICHAIN). I wonder if more helpful properties releavnt to my algorithm could be found? And whether the worst condition may happen?

We represent the poset as a DAG. Notice: We can assume that $G$'s underlying undirected graph is connected. Otherwise, we can calculate each connected component and just multiply the number of each component. Also, we assume that $G$ is transitive reduction of itself, i.e, $G$ is free of transitive edge.

Consider a vertex $u$ of $G$, let $R^+[u]=\{ v | u \leadsto v \}$ denote the set of vertices which are reachable from $u$, including $u$ itself. Similarly, let $R^-[u]=\{ v | v \leadsto u \}$.

  • When $u$ is selected as a member of an antichain, $R^+[u]$ is excluded from further selection, i.e., $G \leftarrow G-R^+[u]$. Just delete $R^+[u]$ and any edge which has an head (ending-point) in $R^+[u]$ from $G$.
  • When $u$ is not selected, $R^-[u]$ is excluded from further selection, i.e., $G \leftarrow G-R^-[u]$. Just delete $R^-[u]$ and any edge which has an tail (starting-point) in $R^-[u]$ from $G$.

Let $|R^+[u]|=a$ and $|R^-[u]|=b$, then the recurrence relation is at least as good as $$T(n)=T(a)+T(n-a)+T(b)+T(n-b) \text.$$

Why at least? Because the underlying undirectd graph of $G-R^+[u]$ or $G-R^-[u]$ may be disconnected.

For a DAG, let ${\Delta^-}(G)$ and ${\Delta^+ }(G) $ represent the maximum indegree and outdegree of vertices of $G$. If ${\Delta ^ - }(G) \le 1$ and ${\Delta ^ + }(G) \le 1$ , then #ANTICHAIN is in $\mathcal{O}(n)$. Otherwise, my algorithm satisfies the recursion

$$T(n)=T(n-1)+T(n-3) \text,$$

nearly $\mathcal{O}(1.45^n)$. I wonder whether the recursion is tight? Does there exists a DAG when using my simple divide-conquer algorithm, the running time is $T(n)=T(n-1)+T(n-3)$?

This algorithm is really kind of stupid. Are there more elegant, effective algorithm exist already? Has anyone thought about the possible FPRAS of it? Or has prove that #ANTICHAIN does not have a FPRAS?

Wow, closed. Sincerely thanks for your answer/comment in advance. ^_^

$\endgroup$
6
$\begingroup$

Counting antichains in an $n$ element poset is equivalent to counting independent sets in a comparability graph on $n$ vertices. The problem of counting the independent sets in an $n$ vertex graph has an $O(1.2461^n)$ time algorithm, see Fürer and Kasiviswanathan http://eccc.hpi-web.de/report/2005/033/ .

$\endgroup$
  • 1
    $\begingroup$ The paper solves #maximum independent set, not #indpendent set. Does the two counting problems the same? $\endgroup$ – Peng Zhang Aug 9 '11 at 12:48
  • 4
    $\begingroup$ Just let the weight function be identically zero. This is not made explicit in the paper, but a later version at cse.psu.edu/%7Ekasivisw/2sat.pdf at least states that #independent sets also can be done in $O(1.2461^n)$ time. $\endgroup$ – Andreas Björklund Aug 9 '11 at 13:50

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.