3
$\begingroup$

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?

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ T could be the set of all nodes, do you mean T should be the smallest size set among all such sets? $\endgroup$
    – Saeed
    Aug 21, 2018 at 7:59
  • $\begingroup$ 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. $\endgroup$
    – Karagounis Z
    Aug 21, 2018 at 17:41
  • $\begingroup$ 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? $\endgroup$
    – Saeed
    Aug 22, 2018 at 10:22
  • $\begingroup$ (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. $\endgroup$
    – Neal Young
    Aug 23, 2018 at 15:08
  • $\begingroup$ @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). $\endgroup$
    – Saeed
    Aug 24, 2018 at 14:49

2 Answers 2

Reset to default
2
$\begingroup$

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

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$

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Karagounis Z
    Aug 25, 2018 at 17:40
  • $\begingroup$ 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...) $\endgroup$
    – Neal Young
    Aug 25, 2018 at 17:51
  • $\begingroup$ 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. $\endgroup$
    – Neal Young
    Aug 25, 2018 at 18:04
  • $\begingroup$ I edited the question to put the modified algorithm. $\endgroup$
    – Karagounis Z
    Aug 26, 2018 at 3:49
0
$\begingroup$

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).

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Neal Young
    Aug 25, 2018 at 14:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.