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.
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:
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;
}
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.
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".
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:
Explanations:
The next three functions count the number of solutions for these MVC problems:
Explanations:
Two notes regarding the implementation:
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With