The number of minimum vertex coatings in a tree

Question

There are [at least] three algorithms that find the minimum vertex coverage in a tree in linear (O (n)) time. I'm interested in modifying all of these algorithms, so I will also get the number of these minimum vertex coverings.

For example, for the P4 tree (path with 4 nodes), the number of MVCs is 3, since we can choose nodes: 1 and 3, 2 and 4, or 2 and 3.

Of course, you can describe a solution for any of the free algorithms - not all 3. I'm just interested in everything, but if you have something to add, feel free to.

I will describe the algorithms that I know to make it easier for you.

1. The greedy algorithm.

We can notice that for each edge it is necessary to include one of the nodes. Which one to choose? Suppose we have an edge with a “normal” node and a leaf. Which node is better to choose? Of course, not a leaf, since another node can help us with one more edge. The algorithm is as follows:

• Start with any node that is not a leaf.
• For each child node, a DFS call is called and when it returns a check if the parent or child is marked as node in the vertex cover. If not, you need to select one of them, so select the parent (and mark it).
• The sheet does nothing.

Here is 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. The dynamic programming algorithm.

We can also use recursion to solve the problem.

 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 in node v, it can be either in MVC or not. If so, we add it to our result 1 (because we include v) and sub-results for subtrees for all v children. If, on the other hand, this is not in MVC, then all his children should be in MVC, so we add the number of children to the result, and for each of the children we add subresult of their children (so v grandchildren). The algorithm is linear, because we check each node 2 times - for our parents and grandfathers.

3. Dynamic programming no 2.

Instead of two states for node v (1 - in MVC, 2 - not in MVC) we can add 3, possibly in MVC. How does this help? First, we call MVC (v = random node, “maybe”) because we don’t know whether v should be in MVC or not. The result for "maybe" is the minimum of the results from "yes" and "no." The result for "yes" is 1 + sum (MVC (child, "maybe") for the child in v.children). And the result for “no” is the sum (MVC (child, “yes”) for the child in v.children). I think it’s pretty clear why. If not, ask in the comments. Therefore, the formula:

 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 each node is checked twice - with yes and no.

Answer 1

Dynamic programming solution

This solution extends according to 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 exactly match your MVC function for possible, no, and yes states. They count the minimum number of vertices that must be included in the vertex wrapper of a subtree below v:

• cover_maybe (v) defines the minimum vertex coverage for a subtree below v.
• cover_no (v): MVC for the subtree below v with the condition that v is not included in this cover.
• cover_yes (v): MVC for a subtree below v with the condition that v be included in this cover.

Explanations:

• cover_maybe (v): In any vertex cover, v is either included in the cover or not. MVC chooses a solution with the minimum number of vertices included: minimum cover_no (v) and cover_yes (v).
• cover_no (v): If v is not included in the cover, all children must be included in the cover (to cover the edges from v to children). Therefore, we need to add the included vertices to cover_yes (child) for all children of v.
• cover_yes (v): Since v is included in the cover, it already covers the edges from v to children --- we do not limit whether to include the child in the cover or not and, therefore, add cover_maybe (child) for all children v.

The following three functions count the number of solutions to these MVC problems:

• count_maybe (v) counts the number of MVC solutions for a subtree below v.
• count_no (v) counts the number of MVC solutions provided that v is not included in the covers.
• count_yes (v) counts the number of MVC solutions under the condition that v is contained in 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 to always exclude v from the cover: count_maybe (v) = count_no (v), Similarly, if cover_yes (v) smaller 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): since we already know whether to include or exclude node v in the cover, we leave it to the child child trees. The number of possible solutions is the result of counting decisions for each subtree. Choosing the right subtask (count_yes or count_maybe) is described above (for cover_no (v) and cover_yes (v)).

Two notes regarding implementation:

• As usual for dynamic programming, you must cache the results of each function: the first time the result is calculated and stored in the cache. When you re-query the same query, the result is read from the cache, and not calculated again. Due to this caching, the execution time of this algorithm is O (n), because each of the six functions can be calculated no more than once for each node.
• You should start the calculation with the root of the tree (not with a random node, as you suggest in your question): despite the fact that the problem is identified with a non-oriented one, our split and win algorithm selects one root node and arranges the child nodes according with their distance from this root.