Number of minimum vertex covers in a tree

Question

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:

1. Start from any node which is not a leaf.
2. 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).
3. For a leaf do nothing.

Here's the code: https://ideone.com/mV4bqg.

#include<stdio.h>
#include<vector>
using namespace std;

vector<int> graph[100019];
int mvc[100019];

int mvc_tree(int v)
{
    mvc[v] = -1;
    if(graph[v].size() == 1)
        return 0;
    int x = 0;
    for(int i = 0; i < graph[v].size(); ++i)
        if(!mvc[graph[v][i]])
        {
            x += mvc_tree(graph[v][i]);
            if(mvc[v] < 1 && mvc[graph[v][i]] < 1)
                ++x,
                mvc[v] = 1;
        }
    return x;
}

int main()
{
    int t, n, a, b, i;

    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        for(i = 1; i <= n; ++i)
            graph[i].clear();
        for(i = 1; i < n; ++i)
        {
            scanf("%d%d", &a, &b);
            graph[a].push_back(b);
            graph[b].push_back(a);
            mvc[i] = 0;
        }
        mvc[n] = 0;
        if(n < 3)
        {
            puts("1");
            continue;
        }
        for(i = 1; i <= n; ++i)
            if(graph[i].size() > 1)
                break;
        printf("%d\n", mvc_tree(i));
    }
    return 0;
}

2. Dynamic programming algorithm.

We can also use recursion to solve the task.

MVC(v) = min(
              1 + sum(MVC(child) for child in v.children),
              v.children.size + sum(MVC(grandchild) for grandchild in v.grandchildren)
            )

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:

MVC(v, "maybe") = min(MVC(v, "yes"), MVC(v, "no"))
MVC(v, "yes") = 1 + sum(MVC(child, "maybe") for child in v.children)
MVC(v, "no") = sum(MVC(child, "yes") for child in v.children)

The complexity is also O(n) because every node is checked twice - with "yes" and with "no".

Tarantula

Answer 1

Dynamic programming solution

This solution expands on your third algorithm "dynamic programming no 2": We recursively define six functions

cover_maybe(v) := min(cover_no(v), cover_yes(v))
cover_no   (v) := sum(cover_yes  (child) for child in v.children)
cover_yes  (v) := sum(cover_maybe(child) for child in v.children) + 1

count_maybe(v) :=
  count_no (v)                  if cover_no(v) < cover_yes(v) 
  count_yes(v)                  if cover_no(v) > cover_yes(v) 
  count_no (v) + count_yes(v)   if cover_no(v) == cover(yes)

count_no   (v) := product(count_yes  (child) for child in v.children)
count_yes  (v) := product(count_maybe(child) for child in v.children)

The first three functions cover_maybe, cover_no and cover_yes precisely correspond to your function MVC for the states "maybe", "no" and "yes". They count the minimum number of vertices that need to be included into a vertex cover of the sub-tree below v:

• cover_maybe(v) determines the minimal vertex cover for the sub-tree below v.
• cover_no(v): MVC for the sub-tree below v with the condition that v is not included in this cover.
• cover_yes(v): MVC for the sub-tree below v with the condition that v is included in this cover.

Explanations:

• cover_maybe(v): In any vertex cover, v is either included in the cover or not. MVC picks a solution with minimal number of included vertices: the minimum of cover_no(v) and cover_yes(v).
• cover_no(v): If v is not included in the cover, then all children must be included in the cover (in order to cover the edges from v to the children). Therefore, we need to add the included vertices in cover_yes(child) for all children of v.
• cover_yes(v): Because v is included in the cover, it already covers the edges from v to the children --- we not restricted whether to include a child into the cover or not and hence add cover_maybe(child) for all children of v.

The next three functions count the number of solutions for these MVC problems:

• count_maybe(v) counts the number of MVC solutions for the sub-tree below v.
• count_no(v) counts the number of MVC solutions with the condition that v is not included in the covers.
• count_yes(v) counts the number of MVC solutions with the condition that v is contained in the covers.

Explanations:

• count_maybe(v): We need to consider three separate cases: If cover_no(v) is less than cover_yes(v), then it is better always to exclude v from the cover: count_maybe(v)=count_no(v). Similarly, if cover_yes(v) is less than cover_no(v), we always include v in the cover and set count_maybe(v)=count_yes(v). But if count_no(v) is equal to count_yes(v) then we can either include or exclude v from the cover. The number of possibilities is the sum: count_maybe(v)=count_no(v)+count_yes(v).
• count_no(v) and count_yes(v): Because we already know whether to include or exclude the node v into the cover, we are left with independent sub-trees for the children. The number of possible solutions is the product of solution counts for each sub-tree. The choice of the correct sub-problem (count_yes or count_maybe) is as explained above (for cover_no(v) and cover_yes(v)).

Two notes regarding the implementation:

• As usual for dynamic programming, you must cache the results of each function: The first time a result is calculated and stored in a cache. When the same query is asked again, then the result is read out of the cache instead of being calculated again. Through this caching, the run time of this algorithm is O(n) because each of the six function can be computed at most once for each node.
• You must start the calculation with the root of the tree (not with a random node as you suggest in your question): Even though the problem is defined with undirected --- our "divide and conquer" algorithm picks one root node and arranges the children of nodes according to their distance from this root.

Immediate