5
$\begingroup$

I don't consider myself very good at math, but nevertheless I enjoy solving optimization problems like the ones often asked in ACM ICPC (a college programming competition). I recently came across an issue while trying to solve one of such problems. I'd appreciate any help to find a linear algorithm (something better than $O(n^2)$ is still OK) for the following problem:

Given a tree $T = (V,E)$ we want to find the size of the smallest set $V'$ such that $V'$ is a subset of $V$ and for every vertex $u$ in $V$ there's at least one vertex $w$ in $V'$ such that $\text{dist}(u,w)$ is less than or equal to $K$, where $K$ is a given natural number.

Here, note that $\text{dist}(u,w)$ is the length of the shortest path from $u$ to $w$ in the tree (in terms of hops), and tree $T$ is unweighted.

I'm very aware that there is a known greedy algorithm for $K=1$, which is in fact the cardinality of the minimum vertex cover. Solving for a general $K$ is what I'm interested in. I thought about several approaches but none of them seem to convince me. Do any of you know how to approach this?

$\endgroup$
2
  • 2
    $\begingroup$ Having read the question properly, this is not really a Vertex Cover variant - VC is about vertices covering edges - this is a special case of Distance Dominating Set. The general problem is of course NP-complete (and W[2]-complete), however I don't know that there's much information regarding distance domination in trees, but that might give you somewhere to start looking. $\endgroup$ – Luke Mathieson May 27 '14 at 5:57
  • $\begingroup$ @LukeMathieson I didn't know about Distance Dominating Sets. Thank you, that's indeed a good point to start.@Raphael I'll change the title accordingly. $\endgroup$ – Alex Pizarro May 27 '14 at 12:20
5
$\begingroup$

Binary, rooted trees

Let's focus first on the case of binary, rooted trees (i.e., every vertex has either 0 or 2 children). This case can be solved in polynomial time using dynamic programming, with subproblems as defined below.

Let me first define some notation that will be helpful. $\newcommand{\dist}{\text{dist}} \newcommand{\dom}{\text{dom}} \newcommand{\gap}{\text{gap}} \newcommand{Ni}{\mathbb{N}_{-\infty}}$ Let $T_v$ denote the set of descendants of $v$, including $v$ itself, i.e., the vertices in the subtree rooted at $v$. If $S$ is a set of vertices, let $\dist(v,S)= \min \{\dist(v,s) : s \in S\}$. Define $\dom(S) = \{v\in V : \exists s \in S . \dist(s,v) \le K\}$; this is the set of vertices dominated by $S$. Finally, let $\gap_v(S) = \max \{\dist(v,w) : w \in T_v \setminus \dom(S)\}$, i.e., the gap of $S$ (with respect to $v$) is the depth of the deepest descendant of $v$ that is not dominated by some node of $S$. Also, define the depth of $S$ (with respect to $v$) to be $\dist(v,S)$. Define $\Ni = \mathbb{N} \cup \{-\infty\} = \{-\infty,0,1,2,3,\dots\}$.

The intuition is that we can build up an optimal dominating set recursively, bottom-up. Let $v_0$ and $v_1$ be the two children of the root, and suppose we have a set $S_0 \subseteq T_{v_0}$ for the left subtree and $S_1 \subseteq T_{v_1}$ for the right subtree. Can we combine $S_0,S_1$ somehow to get a dominating set for the whole tree? To determine the answer to this question, all we need to know about $S_0,S_1$ are their depth and gap (with respect to the root). Therefore, all that matters when searching for a minimum dominating set is their depth, gap, and size. We don't need to enumerate all possibilities for $S_0,S_1$; for each possible combination of depth and gap, we just need to know the minimum attainable size for a set with that depth and gap. This enables us to use dynamic programming effectively.

In particular, we will use the following definition of a subproblem:

INPUT: a vertex $v \in V$, a depth $d \in \Ni$, a gap $g \in \Ni$
OUTPUT: $n(v,d,g)$, defined to be the size of the smallest set $S \subseteq T_v$ of depth $d$ and gap $g$, i.e., the size of the smallest set $S \subseteq T_v$ such that $\dist(v,S)=d$ and $\gap_v(S)=g$

You can use dynamic programming to solve these subproblems, traversing the tree in a bottom-up fashion. If $v$ is a leaf, $n(v,d,g)$ is easy to compute. Next suppose that $v$ is an internal node, with children $w,x$. Then we can compute $n(v,d,g)$ from $n(w,\cdot,\cdot)$ and $n(x,\cdot,\cdot)$ as follows. If $d>0$ and $g\ge 0$, we use the recurrences:

$$n(v,0,-\infty) = \min \{1 + n(w,d',g') + n(x,d'',g'')\}$$

$$n(v,d,-\infty) = \min \{n(w,d-1,-\infty) + n(x,d'',g''), \\ n(w,d'',g'') + n(x,d-1,-\infty) : d'' \ge d-1, d+g''+1 \le K\}.$$

$$n(v,d,g) = \min \{n(w,d',g') + n(x,d'',g'') : \min(d',d'')=d-1, \max(g',g'')=g+1\}.$$

We have some easy base cases when $d\le 0$ or $g=-\infty$: $n(v,-\infty,g) = 0$ if $g = \max\{\dist(v,w) : w \in T_v\}$, or $\infty$ otherwise; $n(v,0,g) = \infty$ if $g \ge 0$.

In the exposition above, $d,g$ are implicitly subject to the constraints that $d \in \{-\infty,0,1,\dots,2K\}$, $g \in \{-\infty,0,1,\dots,K-1\}$, $d \ge 0 \land g \ge 0 \implies d+g > K$, $g \ge 0 \implies d \le g+K+1$, $g=-\infty \implies d \le K$ (since other combinations aren't possible). $d',g'$ and $d'',g''$ are implicitly constrained in the same way.

Finally, the size of the smallest distance-$K$ dominating set for the entire tree is given by $\max \{n(r,d,-\infty)\}$ where $r$ is the root of the tree.

Running time analysis: There are $O(|V| \cdot K^2)$ subproblems. Each recurrence can be computed in $O(K^2)$ time, by organizing the $\min$ computation suitably. Therefore, the total running time is $O(|V| \cdot K^4)$.

Unrooted trees

It is easy to deal with unrooted trees: simply pick an arbitrary vertex to be the root, and now a depth-first search will turn it into a rooted tree. Then you can apply the above algorithm.

Trees of arbitrary branching factor

The above algorithm can be easily generalized to trees whose branching factor at each vertex is $\le 2$ (i.e., each vertex has either 0, 1, or 2 children).

I haven't thought through what happens if the tree might have arbitrary branching factor (i.e., not restricted to $\le 2$). I expect that similar recurrences and subproblems will be applicable. If you organize the $\min$ computations cleverly, you might be able to achieve a low-order-polynomial running time, e.g., $O(|V| \cdot K^c)$ for some small constant $c$ (e.g., $c=4$). However, I haven't worked through the details; I'll leave that to you.

$\endgroup$
2
  • $\begingroup$ Could you clarifiy a couple of things? 1) How would you extend your solution to an unrooted tree? (which is the case) 2) Assuming a rooted tree, the overall answer could be found solving for $n(root,0)$. Would not that force us to always include the root in the solution? 3) After you list down the children of the generic vertex $v$ and provide the transition equation, shouldn't it be from neighbor $w_1$ to $w_i$ in both arguments of $min$? $\endgroup$ – Alex Pizarro May 28 '14 at 0:15
  • $\begingroup$ @AlexPizarro, OK, I've edited my answer to fix the flaw that you pointed out, and tried to respond to your other questions as well. Thank you for pointing out the error in my initial answer! The fix required a more complex algorithm with more ugly cases (sorry), but the overall idea remains similar: try to build up a solution recursively, in a bottom-up fashion, reusing work as much as possible. $\endgroup$ – D.W. May 28 '14 at 19:56

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.