5
$\begingroup$

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.

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

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
2
  • $\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$ Nov 13, 2015 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, 2015 at 20:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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