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.

  • $\begingroup$ 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$? $\endgroup$ – David Richerby Oct 31 '15 at 17:16
  • $\begingroup$ @DavidRicherby it's enough to have one neighbour of $u$ and one neighbor of $v$ is $S$. $\endgroup$ – Steve Madden Oct 31 '15 at 17:38
  • $\begingroup$ Are you guaranteed it is a binary tree? Or is the degree unlimited? $\endgroup$ – D.W. Nov 1 '15 at 1:40
  • $\begingroup$ @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. $\endgroup$ – David Richerby Nov 1 '15 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.

  • $\begingroup$ Could you explain how to express every state? I'm not sure if your solution gives correct answer, for example consider a long path of vertices. $\endgroup$ – Steve Madden Nov 13 '15 at 18:47
  • $\begingroup$ @SteveMadden, can you explain what you mean by "state"? I think it should all work out but I haven't tried to implement or work out all the details of the recurrence so I could always be wrong. Probably a useful next step would be to try to write down the recurrence and then run it by hand on an example (e.g., a tree that's a long path of vertices). $\endgroup$ – D.W. Nov 13 '15 at 20:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.