There are [at least] three algorithms which find minimum vertex cover in a tree in linear (O(n)) time. What I'm interested in is a modification of all of these algorithms so that I'll also get number of these minimum vertex covers.
For example for tree P4 (path with 4 nodes) the number of MVC's is 3 because we can choose nodes: 1 and 3, 2 and 4 or 2 and 3.
Of course you can describe the solution for any of the free algorithms - not all 3. I'm just interested in all of them, but if you have anything to add, don't hesitate.
I'll describe the algorithms that I know to make it easier for you.
1. Greedy algorithm.
We can notice that for every edge we have to include one of the nodes. Which one to choose? Assume we have an edge with "normal" node and a leaf. Which node is better to choose? Not the leaf of course, as the other node might help us with one more edge. The algorithm is as follows:
Start from any node which is not a leaf.
For each child make a DFS call and when it returns check if either parent or child are marked as node in vertex cover. If not you have to choose one of them so choose the parent (and mark it).
For a leaf do nothing.
Here's the code: https://ideone.com/mV4bqg.
2. Dynamic programming algorithm.
We can also use recursion to solve the task.
When we are at node v it can either be in MVC or not. If it is, we add it to our result 1 (because we include v) and subresults for subtrees for all v's children. If, on the other hand, it's not in MVC, then all his children have to be in MVC, so we add to the result number of children and for each of the children we add subresult's of their children (so v's grandchildren).
The algorithm is linear, because we check each node 2 times - for their parent and grandparent.
3. Dynamic programming no 2.
Instead of 2 states for node v (1 - in MVC, 2 - not in MVC) we can make 3 adding "maybe in MVC". How does that help? First, we call MVC(v = random node, "maybe") as we don't know whether v should be in MVC or not. The result for "maybe" is minimum of results from "yes" and "no". The result for "yes" is 1+sum(MVC(child, "maybe") for child in v.children). And the result for "no" is sum(MVC(child, "yes") for child in v.children). I think it's pretty clear why. If not, ask in comments.
The formula is therefore:
The complexity is also O(n) because every node is checked twice - with "yes" and with "no".