Which is the complexity of counting the number of vertex covers of trees? Is it still #P-complete, as for general graphs?


4 Answers 4


The complement of a vertex cover is an independent set. Your question is therefore equivalent to asking whether counting independent sets is #P-complete on trees.

The answer to this question is NO, it is not #P-complete: there is actually a polynomial-time algorithm to count the number of solutions.

  • S. D. Noble, Evaluating a Weighted Graph Polynomial for Graphs of Bounded Tree-Width, The Electronic Journal of Combinatorics 16(1) R64, 2009. (link)

Noble actually shows much more. Suppose the class of graphs under consideration has treewidth at most $k$. Then the weighted graph polynomial $U$, which evaluated at a certain point yields the number of independent sets of a graph, can be evaluated in $O(a_k n^{2k+3})$ operations at any point. Here $a_k$ depends only on $k$ and $n$ is the number of vertices in the input graph. Hence there is a polynomial-time algorithm to count the number of vertex covers on trees (or any other class of graphs of bounded treewidth).

On the other side, it is interesting to ask: what is the smallest class that is known to be #P-complete?

Theorem (Greenhill, 2000): counting independent sets in 3-regular graphs is #P-complete. (link).

In the comments Colin McQuillan pointed out an even stronger result:

Note that wall graphs are 3-regular (if their corners are joined up), bipartite, and planar, but they have arbitrarily large treewidth.

Finally, a different graph polynomial $R_2$ yields the number of independent sets in a bipartite graph. This was posed as an open question:

Question (Ge and Štefankovič, 2010): is the exact evaluation of the $R_2$ polynomial easy for bounded tree-width graphs? (link)

  • 2
    $\begingroup$ Counting independent sets is also #P-hard for bipartite planar 3-regular graphs: Mingji Xia, Wenbo Zhao: #3-Regular Bipartite Planar Vertex Cover is #P-Complete. TAMC 2006: 356-364 $\endgroup$ Mar 21, 2011 at 13:11
  • $\begingroup$ @Colin: wall graphs are bipartite planar 3-regular, so this isn't surprising. Thanks for the pointer! $\endgroup$ Mar 21, 2011 at 14:14

The DP for vertex cover on trees breaks the cases into two disjoint settings, one where the root node of the subtree is picked for the cover, and one where it isn't. This suggests that it should be adaptable to the counting version: the disjointness means you can merely add the contributions from the subcases.

  • $\begingroup$ @Suresh: I was thinking about what happens if we use this approach with a chain tree. In such a case recursively selecting the root should yield an exponential running time. But if we recursively select the middle node of the chain, then the running time is linear. It's amazing how such a slight variation could affect the running time so dramatically. $\endgroup$ Mar 20, 2011 at 20:18
  • 1
    $\begingroup$ What's a chain tree ? $\endgroup$ Mar 21, 2011 at 4:51
  • $\begingroup$ @Suresh: Maybe I've used an "invented" term (although I recall to having heard it in the past). By "chain tree" I mean a tree where every node has exactly one child (except the only one leaf). Example: $V = \{1,2,3,4,5\}$, $E=\{ \{1,2\}, \{2,3\}, \{3,4\}, \{4,5\} \}$. $\endgroup$ Mar 21, 2011 at 9:07
  • $\begingroup$ Ah you mean a path then. $\endgroup$ Mar 21, 2011 at 14:29
  • 1
    $\begingroup$ Moreover what's happening there is the Fibonacci problem, where direct application of recursion from the root causes exponential running time. In this case, and in general, you always work bottom up in the DP to make sure it runs efficiently. $\endgroup$ Mar 21, 2011 at 14:31

Should be in P even on graphs of bounded treewidth


Find any solution in O(N) time using the greedy algorithm (keep moving the leaves, select parent of a leaf if the leaf is not selected or covered.)

Initialize a counter vector to ones for the selected nodes. Check the selected nodes in vertex cover one by one and determine if you release that node and select any of its un-selected neighbors without violating the vertex cover. For each move increase the corresponding counter by one. Number of the vertex cover should be the product of the counter.

(Please let us know if you find any counter example.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.