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?

  • $\begingroup$ (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]? $\endgroup$ Sep 17 '11 at 14:31
  • $\begingroup$ @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. $\endgroup$ Sep 17 '11 at 14:32
  • $\begingroup$ @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. $\endgroup$
    – Thang Dinh
    Sep 17 '11 at 14:34
  • $\begingroup$ 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. $\endgroup$
    – Thang Dinh
    Sep 17 '11 at 14:45
  • 3
    $\begingroup$ 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: ovid.cs.depaul.edu/documents/phcom.ps $\endgroup$ Sep 20 '11 at 3:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.