2
$\begingroup$

Counting the number of solutions is harder than judging the existence of solutions.

Counting independent sets of a graph is notably #P-complete, and so is of a hypergraph.

Two similiar questions in TCS Stack Exchange are here: counting independent sets and does faster exact algorithm for counting independent sets in comparability graph

Moreover, counting independent sets of a given bipartite graph(it is also a comparability graph) is also #P-complete, it doesn't mean counting these is always hard, actually, there are polynomial time (some are linear time) algorithms for cocomparability graphs, trees, permutation graphs, chordal graphs, distance-hereditary graphs, tree convex bipartite graphs, graphs with bounded bipartite pathwidth and so on. There are also some polynomial time approximation algorithms for some types of graphs.

A benign exact exponential algorithm for counting independent sets generally is in fact a direct application of a #2SAT exact algorithm because any undirected graph can be viewed as a special 2CNF where each literal is a pure literal.

How is the progress on counting independent sets of various graphs? Without the help of #2SAT algorithms, it seems hard to design a fast exact algorithms on counting independent sets from a general case of graphs or general bipartite graphs.

There are some surveys telling the progress, but what I can find from papers are all no newer than 2004, which is at least 16 years ago. How is the progress recently? Increasing number of types of graphs have been shown easy for counting, but it is too many and I tend to miss some.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.