<p>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 <a href="http://eccc.hpi-web.de/report/2005/033/" rel="nofollow">http://eccc.hpi-web.de/report/2005/033/</a> .</p>

CC BY-SA 3.0
2011-08-09T12:48:10.223Z
The paper solves #maximum independent set, not  #indpendent set. Does the two counting problems the same?
Peng Zhang
CC BY-SA 3.0
2011-08-09T13:50:55.513Z
Just let the weight function be identically zero. This is not made explicit in the paper, but a later version at http://www.cse.psu.edu/%7Ekasivisw/2sat.pdf at least states that #independent sets also can be done in $O(1.2461^n)$ time.
Andreas Björklund
CC BY-SA 3.0
2011-08-09T08:56:20.857Z
2011-08-10T08:03:39.163Z
2011-08-10T08:03:39.163Z
Andreas Björklund
<p>This post is a little lengthy, thank your for your patience for reading. ^_^</p>

<p>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? </p>

<p>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.</p>

<p>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 \}$. </p>

<ul>
<li>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$. </li>
<li>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$. </li>
</ul>

<p>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.$$</p>

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

<p>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 </p>

<p>$$T(n)=T(n-1)+T(n-3) \text,$$ </p>

<p>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)$?</p>

<p>This algorithm is really kind of <em>stupid</em>. 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? </p>

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

<cc.complexity-theory><ds.algorithms><graph-theory><co.combinatorics><partial-order>
My exact divide-conquer algorithm for counting antichain in a poset?
Peng Zhang
# My exact divide-conquer algorithm for counting antichain in a poset?

(Asked by: username_0 on 2011-08-08)

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. ^\_^

**Tags:** cc.complexity-theory, ds.algorithms, graph-theory, co.combinatorics, partial-order

---

## 1 answers

### Answer by username_1 on 2011-08-09. Score: 6 | Accepted answer

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/> .

> **Comments:**
> **username_0**: The paper solves #maximum independent set, not  #indpendent set. Does the two counting problems the same?  
> **username_1**: Just let the weight function be identically zero. This is not made explicit in the paper, but a later version at http://www.cse.psu.edu/%7Ekasivisw/2sat.pdf at least states that #independent sets also can be done in $O(1.2461^n)$ time.  

---

