<p>The algorithm previously proposed in the post (before the current edit), does not work.</p>

<p>Here are the problem and algorithm proposed in that version of the post:</p>

<p><strong>input:</strong> <em>graph $G=(V,E)$ and the minimum size $k$ of any dominating set in $G$</em></p>

<p><strong>output:</strong> <em>a set of $k$ nodes that dominates a dominating set of size $k$</em></p>

<blockquote>
  <p><strong>algorithm$(G,k)$:</strong></p>
  
  <p>At the start, all nodes are unmarked.</p>
  
  <p>1) Pick an unmarked node $v$ as a center and mark everything within 2
  hops of $v$.  [This step was edited and differs in the current post.]</p>
  
  <p>2) Repeat step 1 until all nodes are marked. (Note, this will never
  place more than $k$ centers)</p>
  
  <p>3) If we have picked less than $k$ centers, keep placing centers on
  undominated nodes until we have placed $k$ centers.</p>
</blockquote>

<hr>

<blockquote>
  <p><strong>Lemma.</strong> <em>The algorithm above doesn't work.</em></p>
</blockquote>

<p><em>Proof.</em> Consider the counter-example $G=(V,E)$ where </p>

<ul>
<li>$V=\{a, b, c, d, e, f\}$</li>
<li>$E=\{(a, b), (a, c), (a, d), (b, e), (c, f), (d, f)\}.$</li>
</ul>

<p><a href="https://i.sstatic.net/FYzNx.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/FYzNx.png" alt="enter image description here"></a></p>

<p>The (unique) minimum dominating set is $\{b, f\}$, with size $k=2$.</p>

<p>The algorithm can place a center on $v=a$ in Step 1 (marking all nodes), then place a center on $e$ in Step 3.  This returns a set $\{a, e\}$ of two centers, neither of which dominates $f$ (which is in the only dominating set of size $2$). $~~~\Box$</p>

<hr>

CC BY-SA 4.0
2018-08-25T17:40:10.327Z
Thank you for your response. This is indeed a counterexample to the proposed algorithm.
I have some ideas for other algorithms but I don't know what the procedure is for asking them. Should I create a new question or modify this one?
Specifically, my idea is that, in step 1 of the algorithm, rather than picking an arbitrary unmarked node, pick the unmarked node which will cover the fewest unmarked nodes when chosen.
Karagounis Z
CC BY-SA 4.0
2018-08-25T17:51:11.357Z
I guess the conventional way would be to write your post so that the post defines the problem, and the post has as its main question determining whether the problem is NP hard or in P.   (I assume that is your goal, as opposed to determining whether a particular algorithm works.)  If you want to discuss possible algorithms, maybe you could open a talk/chat session to do that, and link to it from the post.  (The alternative seems to be to make many posts proposing possible algorithms, most of which probably won't work...)
Neal Young
CC BY-SA 4.0
2018-08-25T18:04:43.737Z
To clarify, I would suggest rewriting your current post rather than creating a new one.  My post won't then be an acceptable answer, but that's fine.
Neal Young
CC BY-SA 4.0
2018-08-26T03:49:20.170Z
I edited the question to put the modified algorithm.
Karagounis Z
CC BY-SA 4.0
2018-08-24T20:22:34.897Z
2018-08-26T13:10:48.393Z
2018-08-26T13:10:48.393Z
Neal Young
<p>I believe that it is NP-Hard to find the desired set. I had a reduction in mind which on second thoughts was buggy. Will update if I manage to fix the argument.</p>

<p>The greedy algorithm considered by the op (which is the same as one of the standard $k$-center $2$-approximation algorithms) shows that one can find a set of size $k$ that dominates a dominating set of $G$ not in $G$ but in $G^2$ (the square of $G$ or equivalently the $2$-hope neighborhood graph).</p>

CC BY-SA 4.0
2018-08-25T14:36:47.643Z
Yes, for the centers found in step 1 of the algorithm, each node in the graph is within distance 2 of one of those centers.  Also, the number of these centers is a lower bound on the minimum dominating set.
Neal Young
CC BY-SA 4.0
2018-08-25T01:13:11.783Z
2018-08-25T02:15:01.453Z
2018-08-25T02:15:01.453Z
Chandra Chekuri
<p>Given an unweighted, undirected graph, a dominating set $S$ is a set of nodes such that every node is in $S$ or adjacent to a node in $S$.</p>

<p>The dominating set problem is NP-hard, but I am considering a new variation.
Given $k$, the size of the minimum dominating set, I need to find a set of nodes $T$ of size at most $k$ such that there exists a minimum dominating set $S$ in the graph which is dominated by $T$. That is, every any node in $S$ should be in $T$ or adjacent to a node in $T$.</p>

<p>My attempt: 
The following is an algorithm I came up with that I have not proven or found a counterexample for.
At the start, all nodes are unmarked.</p>

<p>1) Pick an unmarked node $v$ as a center and mark everything within 2 hops of $v$. EDIT: Instead of picking an arbitrary unmarked node in this step, select the node that would cause the least number of nodes to be marked.</p>

<p>2) Repeat step 1 until all nodes are marked. (Note, this will never place more than $k$ centers)</p>

<p>3) If we have picked less than $k$ centers, keep placing centers on undominated nodes until we have placed $k$ centers.</p>

<p>I have proved that the above algorithm finds a set of centers which dominates a minimum dominating set, under the condition that we don't place any centers in step 3. That is, the algorithm works if steps 1 and 2 manage to place exactly $k$ centers.</p>

<p>Any ideas for whether this algorithm works or a counterexample?</p>

CC BY-SA 4.0
2018-08-21T07:59:25.693Z
T could be the set of all nodes, do you mean T should be the smallest size set among all such sets?
Saeed
CC BY-SA 4.0
2018-08-21T17:41:10.063Z
Actually, I just need a set of nodes of size at most $k$, where $k$ is the size of the min DS. I edited the question.
Karagounis Z
CC BY-SA 4.0
2018-08-22T10:22:56.620Z
Now it is much better, you can also explain what you have done so far and maybe an intuition why this is an interesting question?
Saeed
CC BY-SA 4.0
2018-08-23T15:08:22.467Z
(1) Is $k$ given as part of the input?  (2) Technically, only a *decision-problem* formulation of your problem can be NP-hard. Can you give one?  The obvious one is "*Given $(G=(V,E),k)$, is there a size-$k$ subset $T\subseteq V$ that dominates some dominating set of size $k$?*"  But it's not useful -- the answer is yes iff $G$ has a dominating set of size $k$, so this is just equivalent to Dominating Set.  Maybe "*Given $(G=(V,E),T)$, with $T\subseteq V$, does $T$ dominate some dominating set of size $|T|$?* I believe it is NP-hard... but I'm not sure what that implies about your problem.
Neal Young
CC BY-SA 4.0
2018-08-24T14:49:54.703Z
@NealYoung, I think the question implicitly promises the existence of a dominating set of size $k$. So your first interpretation is not useless (or I don't see why it is useless).
Saeed
CC BY-SA 4.0
2018-08-24T18:22:09.600Z
The post has changed so my comment is no longer relevant.  FWIW my comment (2) above is just about a technical issue -- in the standard def'n of *NP-hard* the problem in question must be a decision problem i.e., a *language*.  But the first language I consider in (2) is _exactly_ Dominating Set, because there exists such a $T$ if and only if there is a dominating set of size $k$ (as you can take $T$ to be the dominating set itself).  As for promise problems, I'm not familiar with whatever standard ways there are of formulating them as decision problems, or of defining them to be NP-hard.
Neal Young
CC BY-SA 4.0
2018-08-25T17:56:18.280Z
FWIW, the greedy Set-Cover algorithm will give you a vertex set of size at most $\lceil k\ln k\rceil$ that dominates *all* vertices (and therefore dominates any dominating set).
Neal Young
CC BY-SA 4.0
2018-08-26T10:43:14.570Z
@NealYoung, what is greedy set cover for this problem? Are you sure it is k log k? Not k log n?
Saeed
CC BY-SA 4.0
2018-08-26T13:06:04.397Z
Whoops, yes, $\lceil k\ln n\rceil$.  (The greedy algorithm in this setting is to repeatedly choose a vertex that dominates the most not-yet-dominated vertices.)
Neal Young
<graph-algorithms><np-hardness><approximation-algorithms>
Finding a set which dominates the Minimum Dominating Set
Karagounis Z
# Finding a set which dominates the Minimum Dominating Set

(Asked by: username_0 on 2018-08-21)

Given an unweighted, undirected graph, a dominating set $S$ is a set of nodes such that every node is in $S$ or adjacent to a node in $S$.

The dominating set problem is NP-hard, but I am considering a new variation.
Given $k$, the size of the minimum dominating set, I need to find a set of nodes $T$ of size at most $k$ such that there exists a minimum dominating set $S$ in the graph which is dominated by $T$. That is, every any node in $S$ should be in $T$ or adjacent to a node in $T$.

My attempt:
The following is an algorithm I came up with that I have not proven or found a counterexample for.
At the start, all nodes are unmarked.

1) Pick an unmarked node $v$ as a center and mark everything within 2 hops of $v$. EDIT: Instead of picking an arbitrary unmarked node in this step, select the node that would cause the least number of nodes to be marked.

2) Repeat step 1 until all nodes are marked. (Note, this will never place more than $k$ centers)

3) If we have picked less than $k$ centers, keep placing centers on undominated nodes until we have placed $k$ centers.

I have proved that the above algorithm finds a set of centers which dominates a minimum dominating set, under the condition that we don't place any centers in step 3. That is, the algorithm works if steps 1 and 2 manage to place exactly $k$ centers.

Any ideas for whether this algorithm works or a counterexample?

**Tags:** graph-algorithms, np-hardness, approximation-algorithms
> **Comments:**
> **username_1**: T could be the set of all nodes, do you mean T should be the smallest size set among all such sets?  
> **username_0**: Actually, I just need a set of nodes of size at most $k$, where $k$ is the size of the min DS. I edited the question.  
> **username_1**: Now it is much better, you can also explain what you have done so far and maybe an intuition why this is an interesting question?  
> **username_2**: (1) Is $k$ given as part of the input?  (2) Technically, only a *decision-problem* formulation of your problem can be NP-hard. Can you give one?  The obvious one is "*Given $(G=(V,E),k)$, is there a size-$k$ subset $T\subseteq V$ that dominates some dominating set of size $k$?*"  But it's not useful -- the answer is yes iff $G$ has a dominating set of size $k$, so this is just equivalent to Dominating Set.  Maybe "*Given $(G=(V,E),T)$, with $T\subseteq V$, does $T$ dominate some dominating set of size $|T|$?* I believe it is NP-hard... but I'm not sure what that implies about your problem.  
> **username_1**: @NealYoung, I think the question implicitly promises the existence of a dominating set of size $k$. So your first interpretation is not useless (or I don't see why it is useless).  
> **username_2**: The post has changed so my comment is no longer relevant.  FWIW my comment (2) above is just about a technical issue -- in the standard def'n of *NP-hard* the problem in question must be a decision problem i.e., a *language*.  But the first language I consider in (2) is _exactly_ Dominating Set, because there exists such a $T$ if and only if there is a dominating set of size $k$ (as you can take $T$ to be the dominating set itself).  As for promise problems, I'm not familiar with whatever standard ways there are of formulating them as decision problems, or of defining them to be NP-hard.  
> **username_2**: FWIW, the greedy Set-Cover algorithm will give you a vertex set of size at most $\lceil k\ln k\rceil$ that dominates *all* vertices (and therefore dominates any dominating set).  
> **username_1**: @NealYoung, what is greedy set cover for this problem? Are you sure it is k log k? Not k log n?  
> **username_2**: Whoops, yes, $\lceil k\ln n\rceil$.  (The greedy algorithm in this setting is to repeatedly choose a vertex that dominates the most not-yet-dominated vertices.)  

---

## 2 answers

### Answer by username_2 on 2018-08-24. Score: 2

The algorithm previously proposed in the post (before the current edit), does not work.

Here are the problem and algorithm proposed in that version of the post:

**input:** *graph $G=(V,E)$ and the minimum size $k$ of any dominating set in $G$*

**output:** *a set of $k$ nodes that dominates a dominating set of size $k$*

> **algorithm$(G,k)$:**
>
> At the start, all nodes are unmarked.
>
> 1) Pick an unmarked node $v$ as a center and mark everything within 2
> hops of $v$. [This step was edited and differs in the current post.]
>
> 2) Repeat step 1 until all nodes are marked. (Note, this will never
> place more than $k$ centers)
>
> 3) If we have picked less than $k$ centers, keep placing centers on
> undominated nodes until we have placed $k$ centers.

---

> **Lemma.** *The algorithm above doesn't work.*

*Proof.* Consider the counter-example $G=(V,E)$ where

* $V=\{a, b, c, d, e, f\}$
* $E=\{(a, b), (a, c), (a, d), (b, e), (c, f), (d, f)\}.$

[![enter image description here](https://i.sstatic.net/FYzNx.png)](https://i.sstatic.net/FYzNx.png)

The (unique) minimum dominating set is $\{b, f\}$, with size $k=2$.

The algorithm can place a center on $v=a$ in Step 1 (marking all nodes), then place a center on $e$ in Step 3. This returns a set $\{a, e\}$ of two centers, neither of which dominates $f$ (which is in the only dominating set of size $2$). $~~~\Box$

---

> **Comments:**
> **username_0**: Thank you for your response. This is indeed a counterexample to the proposed algorithm. I have some ideas for other algorithms but I don't know what the procedure is for asking them. Should I create a new question or modify this one? Specifically, my idea is that, in step 1 of the algorithm, rather than picking an arbitrary unmarked node, pick the unmarked node which will cover the fewest unmarked nodes when chosen.  
> **username_2**: I guess the conventional way would be to write your post so that the post defines the problem, and the post has as its main question determining whether the problem is NP hard or in P.   (I assume that is your goal, as opposed to determining whether a particular algorithm works.)  If you want to discuss possible algorithms, maybe you could open a talk/chat session to do that, and link to it from the post.  (The alternative seems to be to make many posts proposing possible algorithms, most of which probably won't work...)  
> **username_2**: To clarify, I would suggest rewriting your current post rather than creating a new one.  My post won't then be an acceptable answer, but that's fine.  
> **username_0**: I edited the question to put the modified algorithm.  

---

### Answer by username_3 on 2018-08-25. Score: 0

I believe that it is NP-Hard to find the desired set. I had a reduction in mind which on second thoughts was buggy. Will update if I manage to fix the argument.

The greedy algorithm considered by the op (which is the same as one of the standard $k$-center $2$-approximation algorithms) shows that one can find a set of size $k$ that dominates a dominating set of $G$ not in $G$ but in $G^2$ (the square of $G$ or equivalently the $2$-hope neighborhood graph).

> **Comments:**
> **username_2**: Yes, for the centers found in step 1 of the algorithm, each node in the graph is within distance 2 of one of those centers.  Also, the number of these centers is a lower bound on the minimum dominating set.  

---

