Consider the following variation on the vertex cover problem: given a tree on $n$ vertices, we are asked to calculate minimum size of a multiset $S$ such for each edge $(u,v)$ in the tree at least one of the following holds:$u\in S$,$v\in S$,there are at least two vertices in $S$, each of which is adjacent to $u$ or $v$.Since $S$ is a multiset, a vertex may be in $S$ multiple times.My hunch is the following. First of all, we take into consideration the following fact: in optimal solution each vertex is in $S$ at most twice. So we can traverse tree in post-order and calculate results for the three cases where a vertex is not in the optimal $S$, it's in once and it's in twice.Unfortunately I can't link relations between subproblems and I'm not sure if this idea would be correct.Hints or references are both welcome. Many thanks.
A variant of the vertex cover problem on trees
algorithms;graph theory;dynamic programming
Define $f(v,r,s)$ to be the minimum size of a multiset $S$ that covers the entire tree rooted at $v$, such that $S$ contains exactly $r$ copies of $v$'s parent and exactly $s$ copies of $v$.Then you can express $f(v,r,s)$ in terms of the values $f(w_i,s,t_i)$, where the $w_i$'s are the children of $v$.  If the tree is a binary tree, there are only $9=O(1)$ cases you need to consider and at most $2\times 3=O(1)$ terms in the recursive expression for $f(v,r,s)$.  The case analysis gets a bit ugly, but it's all $O(1)$.Therefore, you get a $O(n)$ time algorithm for this problem, if the tree is guaranteed to be a binary tree.  I don't know what happens for general trees of unlimited degree.