Distance k-Dominating Set on a Tree
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&gt;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 &gt; 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.