<p>Bipartite graphs are comparability graphs, and it's known (since Provan and Ball) that counting the number of independent sets in bipartite graphs is #P-complete.</p>

<p>J. S. Provan and M. O. Ball. The complexity of Counting Cuts and of Computing the Probability that a Graph is Connected.  SIAM J. Comput. 12 (1983) 777-788.</p>

<p>If I haven't mistaken, this should answer your question.</p>

CC BY-SA 3.0
2011-08-09T15:43:17.360Z
I'm afraid this wasn't an intended answer.  Probably, I need a clarification on what the "reduction" in the question exactly means.
Yoshio Okamoto
CC BY-SA 3.0
2011-08-09T17:22:42.713Z
I am sorry, I have just edited my question. the older one is not preise.
Peng Zhang
CC BY-SA 3.0
2011-08-09T15:17:12.760Z
2011-08-09T15:17:12.760Z
Yoshio Okamoto
<p>Sorry for not-precise question. :-(</p>

<p>There are several papers concerning exact counting (maximum) independent sets in general graphs. Actually, they concerns counting of solutions of 2SAT. The best of them is $O(1.23^n)$. But the algorithms do not use the specific information of comparability graphs. </p>

<p>So I wonder whether there exists more powerful(faster) exact algorithm for counting independent sets in comparability graphs?</p>

CC BY-SA 3.0
2011-08-09T16:56:09.953Z
Please state your question precisely, but that sounds like a duplicate of [this question](http://cstheory.stackexchange.com/questions/7637/is-counting-maximal-cliques-in-an-incomparability-graph-p-complete).
Tsuyoshi Ito
<graph-theory><co.combinatorics><counting-complexity>
Does faster exact algorithm for counting independent sets in comparability graphs than general graph exisits?
Peng Zhang
# Does faster exact algorithm for counting independent sets in comparability graphs than general graph exisits?

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

Sorry for not-precise question. :-(

There are several papers concerning exact counting (maximum) independent sets in general graphs. Actually, they concerns counting of solutions of 2SAT. The best of them is $O(1.23^n)$. But the algorithms do not use the specific information of comparability graphs.

So I wonder whether there exists more powerful(faster) exact algorithm for counting independent sets in comparability graphs?

**Tags:** graph-theory, co.combinatorics, counting-complexity
> **Comments:**
> **username_1**: Please state your question precisely, but that sounds like a duplicate of [this question](http://cstheory.stackexchange.com/questions/7637/is-counting-maximal-cliques-in-an-incomparability-graph-p-complete).  

---

## 1 answers

### Answer by username_2 on 2011-08-09. Score: 5

Bipartite graphs are comparability graphs, and it's known (since Provan and Ball) that counting the number of independent sets in bipartite graphs is #P-complete.

J. S. Provan and M. O. Ball. The complexity of Counting Cuts and of Computing the Probability that a Graph is Connected. SIAM J. Comput. 12 (1983) 777-788.

If I haven't mistaken, this should answer your question.

> **Comments:**
> **username_2**: I'm afraid this wasn't an intended answer.  Probably, I need a clarification on what the "reduction" in the question exactly means.  
> **username_0**: I am sorry, I have just edited my question. the older one is not preise.  

---

