0
$\begingroup$

I am working on an NP-Complete problem, i.e., the dominating set. Given a graph $G = (V, E)$, a set $S$ is a dominating set if every vertex $v \in V \setminus S$ has at least one neighbor in $S$. I am looking for the complexity of the problem in trees. I have tried the greedy method to solve this problem. But, looks like a greedy algorithm would not work on trees. Is the problem polynomial time solvable? If yes, could someone point me to any references to this result?

$\endgroup$
1

1 Answer 1

2
$\begingroup$

The problem is solvable in linear time by dynamic programming.

Root a the input tree $T$ in an arbitrary vertex and let $T_v$ be the subtree of $T$ rooted in v.

Let $OPT[v]$ denote the size of a minimum dominating set of $T_v$. Let $OPT^-[v]$ denote the minimum size of a subset of vertices of $T_v$ that dominates all vertices in $T_v$ except, possibly, for $v$. Finally, let $OPT^+[v]$, denote the size of a minimum dominating set of $T_v$ that necessarily includes $v$.

If $v$ is a leaf then $OPT[v]= OPT^+[v] = 1$ and $OPT^-[v] = 0$.

Otherwise let $u_1, \dots, u_k$ be the children of $v$ in $T$. $$ OPT^+[v] = 1 +\sum_{i=1}^k OPT^-[u_i] $$

$$ OPT^-[v] = \min\{OPT^+[v], \sum_{i=1}^k OPT[u_i] \} $$

$$ OPT[v] = \min \begin{cases} OPT^+[v]; \\ \min_{j=1,\dots,k} \left( OPT^+[u_j] + \sum_{\substack{i=1,\dots,k \\ i \neq j} } OPT[u_i] \right). \end{cases} $$

Notice that the above formulas for $v$ can be evaluated in time $O(k)$. The only one for which this might not be obvious is the second argument of the minimum in $OPT[v]$. This can be handled by first computing $S = \sum_{i=1}^k OPT[u_i]$ (in $O(k)$ time) and then noticing that, for a $j=1,\dots, k$, the desired quantity can be found in constant time as $S - OPT[u_j] + OPT^+[u_j]$.

$\endgroup$

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.