6
$\begingroup$

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

$\endgroup$
11
$\begingroup$

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)

$\endgroup$
  • 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$ – Colin McQuillan Mar 21 '11 at 13:11
  • $\begingroup$ @Colin: wall graphs are bipartite planar 3-regular, so this isn't surprising. Thanks for the pointer! $\endgroup$ – András Salamon Mar 21 '11 at 14:14
10
$\begingroup$

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.

$\endgroup$
  • $\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$ – Giorgio Camerani Mar 20 '11 at 20:18
  • 1
    $\begingroup$ What's a chain tree ? $\endgroup$ – Suresh Venkat Mar 21 '11 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$ – Giorgio Camerani Mar 21 '11 at 9:07
  • $\begingroup$ Ah you mean a path then. $\endgroup$ – Suresh Venkat Mar 21 '11 at 14:29
  • $\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$ – Suresh Venkat Mar 21 '11 at 14:31
2
$\begingroup$

Should be in P even on graphs of bounded treewidth

$\endgroup$

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.