3
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Please state your question precisely, but that sounds like a duplicate of this question. $\endgroup$
    – Tsuyoshi Ito
    Aug 9 '11 at 16:56
5
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ I'm afraid this wasn't an intended answer. Probably, I need a clarification on what the "reduction" in the question exactly means. $\endgroup$
    – Yoshio Okamoto
    Aug 9 '11 at 15:43
  • $\begingroup$ I am sorry, I have just edited my question. the older one is not preise. $\endgroup$
    – Peng Zhang
    Aug 9 '11 at 17:22

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.