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.