<p>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. </p>

CC BY-SA 2.5
2011-03-20T20:18:27.870Z
@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.
Giorgio Camerani
CC BY-SA 2.5
2011-03-21T04:51:20.247Z
What's a chain tree ?
Suresh Venkat
CC BY-SA 2.5
2011-03-21T09:07:24.593Z
@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\} \}$.
Giorgio Camerani
CC BY-SA 2.5
2011-03-21T14:29:12.517Z
Ah you mean a path then.
Suresh Venkat
CC BY-SA 2.5
2011-03-21T14:31:33.060Z
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.
Suresh Venkat
CC BY-SA 2.5
2011-03-21T16:25:27.090Z
@Suresh: Yes a path! From now on, I'll use the word "path" instead of "chain tree" ;-)
Giorgio Camerani
CC BY-SA 2.5
2011-03-21T16:31:45.427Z
@Suresh: I didn't get the connection with the Fibonacci problem...cool, I'll check it in further detail. Three final questions: 1) By "DP" you mean "Decision Procedure"? 2) What do you exactly mean _in this case_ by "working bottom up"? 3) Is the path case the only case where exponential running time may occur?
Giorgio Camerani
CC BY-SA 2.5
2011-03-21T17:59:08.860Z
0) If you start from the end of the path (the "root"), then the recurrence for the number of covers is T(n) = T(n-1) + T(n-2) - which gives Fibonacci. 1) DP = dynamic program 2) in this case, working bottom up would be working from the other end of the path backward 3) you can get exponential running times from badly unwound recursion in other cases as well I'd imagine.
Suresh Venkat
CC BY-SA 2.5
2011-03-19T20:09:02.850Z
2011-03-19T20:09:02.850Z
Suresh Venkat
<p>Should be in P even on graphs of bounded treewidth</p>

CC BY-SA 2.5
2011-03-19T20:05:40.240Z
2011-03-19T20:05:40.240Z
XXYYXX
<p>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.)</p>
<p>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.</p>
<p>(Please let us know if you find any counter example.)</p>

CC BY-SA 4.0
2020-06-20T14:02:03.177Z
2020-06-20T14:02:03.177Z
Osman Ay
<p>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.</p>

<p>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.</p>

<ul>
<li>S. D. Noble, <em>Evaluating a Weighted Graph Polynomial for 
Graphs of Bounded Tree-Width</em>, The Electronic Journal of Combinatorics <strong>16</strong>(1) R64, 2009. (<a href="http://www.emis.ams.org/journals/EJC/Volume_16/PDF/v16i1r64.pdf">link</a>)</li>
</ul>

<p>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).</p>

<hr>

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

<blockquote>
  <p><em>Theorem (Greenhill, 2000):</em> counting independent sets in 3-regular graphs is #P-complete. (<a href="http://link.aip.org/link/?SMJCAT/12/777/1">link</a>).</p>
</blockquote>

<p>In the comments Colin McQuillan pointed out an even stronger result:</p>

<ul>
<li>Mingji Xia, Wenbo Zhao, <a href="http://dx.doi.org/10.1007/11750321_34"><em>#3-Regular Bipartite Planar Vertex Cover is #P-Complete</em></a>, TAMC 2006, 356–364.</li>
</ul>

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

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

<blockquote>
  <p><em>Question (Ge and Štefankovič, 2010):</em> is the exact evaluation of the $R_2$ polynomial easy for bounded tree-width graphs? (<a href="http://drops.dagstuhl.de/opus/volltexte/2010/2867/pdf/21.pdf">link</a>)</p>
</blockquote>

CC BY-SA 2.5
2011-03-21T13:11:24.593Z
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
Colin McQuillan
CC BY-SA 2.5
2011-03-21T14:14:56.947Z
@Colin: wall graphs are bipartite planar 3-regular, so this isn't surprising.  Thanks for the pointer!
András Salamon
CC BY-SA 2.5
2011-03-19T21:32:34.597Z
2011-03-21T14:30:36.293Z
2011-03-21T14:30:36.293Z
András Salamon
<p>Which is the complexity of counting the number of vertex covers of trees? Is it still #P-complete, as for general graphs?</p>

<cc.complexity-theory><graph-theory><counting-complexity>
Trees: complexity of counting the number of vertex covers
Giorgio Camerani
# Trees: complexity of counting the number of vertex covers

(Asked by: username_0 on 2011-03-19)

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

**Tags:** cc.complexity-theory, graph-theory, counting-complexity


---

## 4 answers

### Answer by username_4 on 2011-03-19. Score: 14 | Accepted answer

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](http://www.emis.ams.org/journals/EJC/Volume_16/PDF/v16i1r64.pdf))

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](http://link.aip.org/link/?SMJCAT/12/777/1)).

In the comments username_5 pointed out an even stronger result:

* Mingji Xia, Wenbo Zhao, [*#3-Regular Bipartite Planar Vertex Cover is #P-Complete*](http://dx.doi.org/10.1007/11750321_34), TAMC 2006, 356–364.

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](http://drops.dagstuhl.de/opus/volltexte/2010/2867/pdf/21.pdf))

> **Comments:**
> **username_5**: 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  
> **username_4**: @Colin: wall graphs are bipartite planar 3-regular, so this isn't surprising.  Thanks for the pointer!  

---

### Answer by username_1 on 2011-03-19. Score: 12

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.

> **Comments:**
> **username_0**: @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.  
> **username_1**: What's a chain tree ?  
> **username_0**: @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\} \}$.  
> **username_1**: Ah you mean a path then.  
> **username_1**: 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.  
> **username_0**: @Suresh: Yes a path! From now on, I'll use the word "path" instead of "chain tree" ;-)  
> **username_0**: @Suresh: I didn't get the connection with the Fibonacci problem...cool, I'll check it in further detail. Three final questions: 1) By "DP" you mean "Decision Procedure"? 2) What do you exactly mean _in this case_ by "working bottom up"? 3) Is the path case the only case where exponential running time may occur?  
> **username_1**: 0) If you start from the end of the path (the "root"), then the recurrence for the number of covers is T(n) = T(n-1) + T(n-2) - which gives Fibonacci. 1) DP = dynamic program 2) in this case, working bottom up would be working from the other end of the path backward 3) you can get exponential running times from badly unwound recursion in other cases as well I'd imagine.  

---

### Answer by username_2 on 2011-03-19. Score: 2

Should be in P even on graphs of bounded treewidth


---

### Answer by username_3 on 2020-06-20. Score: -2

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.)


---

