13
$\begingroup$

This question is motivated by a MathOverflow question by Peng Zhang. 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.

$\endgroup$
11
$\begingroup$

According to this abstract 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.

$\endgroup$
  • $\begingroup$ @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. $\endgroup$ – Tsuyoshi Ito Aug 6 '11 at 16:14
  • $\begingroup$ @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. $\endgroup$ – Tsuyoshi Ito Aug 6 '11 at 16:24
  • $\begingroup$ @Tsuyoshi: you are right, the Provan/Ball paper only shows that counting maximum-cardinality antichains is #P-hard. Back to the drawing board... $\endgroup$ – András Salamon Aug 6 '11 at 16:56
  • 8
    $\begingroup$ 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. $\endgroup$ – Timothy Chow Aug 7 '11 at 2:46

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.