# A variant of the vertex cover problem on trees

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.

• To clarify, is it enough to have one neighbour of $u$ in $S$ and one neighbour of $v$? Or do I need two neighbours of $u$ or two neighbours of $v$? Oct 31, 2015 at 17:16
• @DavidRicherby it's enough to have one neighbour of $u$ and one neighbor of $v$ is $S$. Oct 31, 2015 at 17:38
• Are you guaranteed it is a binary tree? Or is the degree unlimited?
– D.W.
Nov 1, 2015 at 1:40
• @D.W. In the context of graph theory (rather than, say, data structures), a tree is just an undirected, acyclic graph. If there was a degree bound, it would be clearly stated. Nov 1, 2015 at 9:15

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.