<p>Consider the following min-max problem</p>

<p>Given a graph $G=(V,E)$ and an integer $k \geq 0$, delete at most $k$ nodes in $G$ to maximize the size of the minimum dominating set in the residual graph. </p>

<p>The NP-hardness of the problem can be shown by setting $k=0$. Can we somehow easily get the hardness of approximation results from the hardness of the Dominating Set problem? In general, for min-max problems, can we do the same thing?</p>

CC BY-SA 3.0
2011-09-17T14:31:25.447Z
(1) Useful?  Need?  For whom?  (2) “Believed to be not in NP” does not mean much if there is no ground for that belief.  The important part is the _reason_ why it is believed not to be in NP.  (3) Why is this question tagged with [approximation-hardness]?
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-17T14:32:07.303Z
@George: Not being in NP does not imply NP-hardness.  But _the reason why the problem is believed not to be in NP_ might imply NP-hardness.
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-17T14:34:54.303Z
@Tsuyoshi Ito: Thank you for your comment. You are right. I have revised the question to reflect that I don't know to prove that the problem is in NP.
Thang Dinh
CC BY-SA 3.0
2011-09-17T14:45:41.300Z
The reason I asked this questions is that I have seen few papers with NP-hard proofs for min-max problems in which the max problems are already NP-hard. I wonder if I should put such kind of proof into my future writing.
Thang Dinh
CC BY-SA 3.0
2011-09-17T14:55:01.180Z
I have trouble understanding your problem.  What is k?  Isn’t the problem obviously NP-hard by fixing k=0?
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-17T14:58:37.173Z
I guess a similar question is asked here. http://cstheory.stackexchange.com/questions/5591/is-minimax-problem-np-hard-when-the-inner-problem-is-np-hard  My point is that is this always trivial to show the NP-hardness if the inner problem is already NP-hard?  Similarly, is it always trivial to show the same hardness-results of the inner problem for the min-max problem?
Thang Dinh
CC BY-SA 3.0
2011-09-17T15:07:14.660Z
You ignored my question “What is k?” (as well as a few others of my questions).  Without an answer, I am afraid that I will not be able to help you.
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-17T15:09:41.390Z
I'm sorry for all the confusions. I have revised the question again and hopefully it's clearer now. $k$ here is a positive number and a part of the input.
Thang Dinh
CC BY-SA 3.0
2011-09-17T15:19:36.760Z
Thank you for clarifying the question.  In the approximation version, is k still part of the input?  If so, you can still restrict k to 0 and apply the hardness of approximating dominating set.  (This is a typical NP-hardness proof based on restriction, which is most likely to be covered in an undergraduate course in complexity theory.)
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-17T15:25:11.220Z
IMHO, the hardness of approximation cannot be proved through the restriction $k=0$. If $k=0$, then the solution that deletes $0$ vertices, is optimal.
Thang Dinh
CC BY-SA 3.0
2011-09-17T15:36:24.203Z
I do not know what you mean in the last comment.
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-17T15:42:43.530Z
First, thank you for bearing with me :-) If you cannot delete any nodes, then the size of the "maximum" dominating set does not change. The question is asked for modifying the graph to maximize the size of the maximum dominating set. If the optimal delete $k$ vertices to get an DS of size $D_\mbox{opt}$ and an other solution deletes $k$ vertices to get a maximum dominating set of size $D_\mbox{approx}$ then the approximation ratio will be $D_\mbox{opt}/ D_\mbox{approx}$.
Thang Dinh
CC BY-SA 3.0
2011-09-17T15:50:05.940Z
Let me check whether I understand your problem.  As I understand it (from your latest comment), you do not require the size of the minimum dominating set after removal of k nodes (which is already hard to compute even if k=0), but you only require _which nodes to remove_ to maximize the minimum dominating set (which is trivial to compute if k=0, because the answer is always “remove no nodes” no matter what the minimum dominating set in the graph is).  Did I get your problem right this time?
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-17T15:53:52.443Z
By the way, do you mean _minimum_ dominating set when you write “maximum dominating set” (whose literal meaning would be the set of all vertices)?
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-17T15:54:09.620Z
Yes, it is. The problem asks for the set of the vertices to remove.   If I'm not wrong the problem is in P^NP that's why I "suspected" it might be "hard" to show it is in NP.
Thang Dinh
CC BY-SA 3.0
2011-09-17T15:57:21.520Z
Sorry, I mean the Minimum not Maximum DS
Thang Dinh
CC BY-SA 3.0
2011-09-17T16:02:31.017Z
Sorry for continuing comments, but I am still confused.  If I understand the problem, then setting k=0 does not prove the NP-hardness of the exact (non-approximation) case, contradicting what you added to the question in revision 4.  If you added just because I said so, my comment referred to the case where you have to compute the size of minimum dominating set, and it does not apply to your actual question, no matter whether you consider approximation or not.
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-17T16:10:02.087Z
Please correct me if I'm wrong setting $k=0$ does prove the NP-hardness assuming the decision version of the problem is $(G, k, d)$ - Can we delete $k$ vertices from $G$ so that the DS has size at least $d$. But it cannot be applied to the inapproximability proof.
Thang Dinh
CC BY-SA 3.0
2011-09-17T16:19:14.387Z
Well, that particular way of converting your problem to a decision problem does not work if you do not care the size of minimum dominating set.  (By the way, you should say “minimum DS” instead of just “DS.”)  I cannot see immediately how to convert your problem to a decision problem, but conversion to a decision problem is orthogonal to whether you consider the exact or the approximation version.
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-17T16:28:25.627Z
@Tsuyoshi Ito: Thank you very much and really appreciate your time.  I have to go now and gonna spend more thought for the question before any asking.
Thang Dinh
CC BY-SA 3.0
2011-09-20T03:00:24.580Z
So it sounds like the problem is: given an integer $k$, and a graph $G = (V, E)$, compute the $\ell \leq k$, $I = \{v_1, ..., v_\ell\}$ vertices that maximize the size of the minimum dominating set (MDS) of the subgraph induced on $V - I$. And then if an algorithm outputs a solution $I$ and the optimal solution is $I_{opt}$, the approximation ratio is $|MDS(G- I_{OPT})|/|MDS(G-I)|$. Note that the algorithm does not have to output $|MDS(G-I)|$. The survery of completeness in the higher levels of PH of Umans ans Shaefer might help: http://ovid.cs.depaul.edu/documents/phcom.ps
Sasho Nikolov
<cc.complexity-theory><np-hardness><approximation-hardness>
Hardness of min-max problems
Thang Dinh
# Hardness of min-max problems

(Asked by: username_0 on 2011-09-17)

Consider the following min-max problem

Given a graph $G=(V,E)$ and an integer $k \geq 0$, delete at most $k$ nodes in $G$ to maximize the size of the minimum dominating set in the residual graph.

The NP-hardness of the problem can be shown by setting $k=0$. Can we somehow easily get the hardness of approximation results from the hardness of the Dominating Set problem? In general, for min-max problems, can we do the same thing?

**Tags:** cc.complexity-theory, np-hardness, approximation-hardness

> **Comments:**
> **username_1**: (1) Useful?  Need?  For whom?  (2) “Believed to be not in NP” does not mean much if there is no ground for that belief.  The important part is the _reason_ why it is believed not to be in NP.  (3) Why is this question tagged with [approximation-hardness]?  
> **username_1**: @George: Not being in NP does not imply NP-hardness.  But _the reason why the problem is believed not to be in NP_ might imply NP-hardness.  
> **username_0**: @username_1: Thank you for your comment. You are right. I have revised the question to reflect that I don't know to prove that the problem is in NP.  
> **username_0**: The reason I asked this questions is that I have seen few papers with NP-hard proofs for min-max problems in which the max problems are already NP-hard. I wonder if I should put such kind of proof into my future writing.  
> **username_1**: I have trouble understanding your problem.  What is k?  Isn’t the problem obviously NP-hard by fixing k=0?  
> **username_0**: I guess a similar question is asked here. http://cstheory.stackexchange.com/questions/5591/is-minimax-problem-np-hard-when-the-inner-problem-is-np-hard  My point is that is this always trivial to show the NP-hardness if the inner problem is already NP-hard?  Similarly, is it always trivial to show the same hardness-results of the inner problem for the min-max problem?  
> **username_1**: You ignored my question “What is k?” (as well as a few others of my questions).  Without an answer, I am afraid that I will not be able to help you.  
> **username_0**: I'm sorry for all the confusions. I have revised the question again and hopefully it's clearer now. $k$ here is a positive number and a part of the input.  
> **username_1**: Thank you for clarifying the question.  In the approximation version, is k still part of the input?  If so, you can still restrict k to 0 and apply the hardness of approximating dominating set.  (This is a typical NP-hardness proof based on restriction, which is most likely to be covered in an undergraduate course in complexity theory.)  
> **username_0**: IMHO, the hardness of approximation cannot be proved through the restriction $k=0$. If $k=0$, then the solution that deletes $0$ vertices, is optimal.  
> **username_1**: I do not know what you mean in the last comment.  
> **username_0**: First, thank you for bearing with me :-) If you cannot delete any nodes, then the size of the "maximum" dominating set does not change. The question is asked for modifying the graph to maximize the size of the maximum dominating set. If the optimal delete $k$ vertices to get an DS of size $D_\mbox{opt}$ and an other solution deletes $k$ vertices to get a maximum dominating set of size $D_\mbox{approx}$ then the approximation ratio will be $D_\mbox{opt}/ D_\mbox{approx}$.  
> **username_1**: Let me check whether I understand your problem.  As I understand it (from your latest comment), you do not require the size of the minimum dominating set after removal of k nodes (which is already hard to compute even if k=0), but you only require _which nodes to remove_ to maximize the minimum dominating set (which is trivial to compute if k=0, because the answer is always “remove no nodes” no matter what the minimum dominating set in the graph is).  Did I get your problem right this time?  
> **username_1**: By the way, do you mean _minimum_ dominating set when you write “maximum dominating set” (whose literal meaning would be the set of all vertices)?  
> **username_0**: Yes, it is. The problem asks for the set of the vertices to remove.   If I'm not wrong the problem is in P^NP that's why I "suspected" it might be "hard" to show it is in NP.  
> **username_0**: Sorry, I mean the Minimum not Maximum DS  
> **username_1**: Sorry for continuing comments, but I am still confused.  If I understand the problem, then setting k=0 does not prove the NP-hardness of the exact (non-approximation) case, contradicting what you added to the question in revision 4.  If you added just because I said so, my comment referred to the case where you have to compute the size of minimum dominating set, and it does not apply to your actual question, no matter whether you consider approximation or not.  
> **username_0**: Please correct me if I'm wrong setting $k=0$ does prove the NP-hardness assuming the decision version of the problem is $(G, k, d)$ - Can we delete $k$ vertices from $G$ so that the DS has size at least $d$. But it cannot be applied to the inapproximability proof.  
> **username_1**: Well, that particular way of converting your problem to a decision problem does not work if you do not care the size of minimum dominating set.  (By the way, you should say “minimum DS” instead of just “DS.”)  I cannot see immediately how to convert your problem to a decision problem, but conversion to a decision problem is orthogonal to whether you consider the exact or the approximation version.  
> **username_0**: @username_1: Thank you very much and really appreciate your time.  I have to go now and gonna spend more thought for the question before any asking.  
> **username_2**: So it sounds like the problem is: given an integer $k$, and a graph $G = (V, E)$, compute the $\ell \leq k$, $I = \{v_1, ..., v_\ell\}$ vertices that maximize the size of the minimum dominating set (MDS) of the subgraph induced on $V - I$. And then if an algorithm outputs a solution $I$ and the optimal solution is $I_{opt}$, the approximation ratio is $|MDS(G- I_{OPT})|/|MDS(G-I)|$. Note that the algorithm does not have to output $|MDS(G-I)|$. The survery of completeness in the higher levels of PH of Umans ans Shaefer might help: http://ovid.cs.depaul.edu/documents/phcom.ps  

---

## 0 answers

