My exact divide-conquer algorithm for counting antichain in a poset? 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. ^_^
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/ .