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.