Distance k-Dominating Set on a Tree

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?

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.

StackExchange Computer Science Q#26136, answer score: 5