<p>According to <a href="http://epubs.siam.org/sicomp/resource/1/smjcat/v12/i4/p777_s1?isAuthorized=no">this abstract</a> for "The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected" (SIAM J. Comput. 12 (1983), pp. 777-788), counting anti-chains in a partial order is #P-complete. I don't have access to this paper so I can't tell if this result covers maximal anti-chains or not.</p>

CC BY-SA 3.0
2011-08-06T16:14:45.723Z
@András: I think that their result is about counting antichains (which are not necessarily maximal).  It might be easy to see that counting maximal antichains is also #P-complete, but I cannot see it.
Tsuyoshi Ito
CC BY-SA 3.0
2011-08-06T16:24:33.263Z
@András: The question is about maximal antichains, not maximum-cardinality antichains.  I have not studied the reduction in the paper, so maybe their reduction also proves the #P-completeness of counting maximal antichains at the same time, but at least they are different problems.
Tsuyoshi Ito
CC BY-SA 3.0
2011-08-06T16:56:22.513Z
@Tsuyoshi: you are right, the Provan/Ball paper only shows that counting maximum-cardinality antichains is #P-hard.  Back to the drawing board...
András Salamon
CC BY-SA 3.0
2011-08-07T02:46:31.397Z
Actually, if you look at the proof, you'll see that #P-completeness is proved for a class of posets in which all maximal antichains have the same cardinality. Namely, start with any bipartite graph $G=(V,E)$ with $n$ vertices and construct a bipartite graph $G'$ with $2n$ vertices by adding $n$ new vertices $\{v' : v\in V\}$ and $n$ new edges $\{(v,v'): v\in V\}$.  Then, if $V_1$ and $V_2$ is a bipartition of the vertex set of $G'$, define a poset on $V_1\cup V_2$ by setting $x<y$ if $x\in V_1$ and $y\in V_2$ and $x$ and $y$ are adjacent in $G'$. So this does answer my question.
Timothy Chow
CC BY-SA 3.0
2011-08-06T00:29:58.573Z
2011-08-06T00:29:58.573Z
mhum
<p>This question is motivated by a <a href="https://mathoverflow.net/questions/71994/what-is-the-number-of-maximal-antichain-in-a-poset/72033#72033">MathOverflow question by Peng Zhang</a>.  Valiant showed that counting maximal cliques in a general graph is #P-complete, but what if we restrict to incomparability graphs (i.e., we want to count maximal antichains in a finite poset)?  This question seems natural enough that I suspect that it has been considered before, but I have not been able to locate it in the literature.</p>

<cc.complexity-theory><counting-complexity><partial-order><clique>
Is counting maximal cliques in an incomparability graph #P-complete?
Timothy Chow
# Is counting maximal cliques in an incomparability graph #P-complete?

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

This question is motivated by a [MathOverflow question by Peng Zhang](https://mathoverflow.net/questions/71994/what-is-the-number-of-maximal-antichain-in-a-poset/72033#72033). Valiant showed that counting maximal cliques in a general graph is #P-complete, but what if we restrict to incomparability graphs (i.e., we want to count maximal antichains in a finite poset)? This question seems natural enough that I suspect that it has been considered before, but I have not been able to locate it in the literature.

**Tags:** cc.complexity-theory, counting-complexity, partial-order, clique


---

## 1 answers

### Answer by username_1 on 2011-08-06. Score: 11 | Accepted answer

According to [this abstract](http://epubs.siam.org/sicomp/resource/1/smjcat/v12/i4/p777_s1?isAuthorized=no) for "The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected" (SIAM J. Comput. 12 (1983), pp. 777-788), counting anti-chains in a partial order is #P-complete. I don't have access to this paper so I can't tell if this result covers maximal anti-chains or not.

> **Comments:**
> **username_2**: @András: I think that their result is about counting antichains (which are not necessarily maximal).  It might be easy to see that counting maximal antichains is also #P-complete, but I cannot see it.  
> **username_2**: @András: The question is about maximal antichains, not maximum-cardinality antichains.  I have not studied the reduction in the paper, so maybe their reduction also proves the #P-completeness of counting maximal antichains at the same time, but at least they are different problems.  
> **username_3**: @Tsuyoshi: you are right, the Provan/Ball paper only shows that counting maximum-cardinality antichains is #P-hard.  Back to the drawing board...  
> **username_0**: Actually, if you look at the proof, you'll see that #P-completeness is proved for a class of posets in which all maximal antichains have the same cardinality. Namely, start with any bipartite graph $G=(V,E)$ with $n$ vertices and construct a bipartite graph $G'$ with $2n$ vertices by adding $n$ new vertices $\{v' : v\in V\}$ and $n$ new edges $\{(v,v'): v\in V\}$.  Then, if $V_1$ and $V_2$ is a bipartition of the vertex set of $G'$, define a poset on $V_1\cup V_2$ by setting $x<y$ if $x\in V_1$ and $y\in V_2$ and $x$ and $y$ are adjacent in $G'$. So this does answer my question.  

---

