<p>This should be a comment, since it does not directly answer your question, but a related question. Perhaps that a similar trick from [1] will provide you with an answer.</p>

<p>In [1] the following is proven:</p>

<p>Given a graph $G=(V,E)$ and a parameter $k$. There is no FPT algorithm (parameterized by $k$) that either: (a) returns an independent dominating set in $G$ of size at least $g(k)$, where $g(k)$ is a fixed function only depending on $k$ or (b) determines that $G$ does not have a dominating set of size $k$. (...Unless FPT = W[2].)</p>

<p>Any polynomial time algorithm that returns an independent dominating set of size at least $g(k)$, implies at least that FPT = W[2].</p>

<p>[1] Rodney G. Downey, Michael R. Fellows, Catherine McCartin and Frances Rosamond. "Parameterized Approximation of Dominating Set Problems". Information Processing Letters, Volume 109 Issue 1, December, 2008.</p>

CC BY-SA 2.5
2011-03-30T05:59:57.357Z
The trick in [1] is based on the fact that Independent Dominating Set as a maximization problem is not monotone: a subset of a feasible solution is not necessarily a feasible solution (which is usually the case for maximization problems having meaningful approximations). Therefore, it is very well possible that every feasible solution has the same size, making approximation irrelevant.
Daniel Marx
CC BY-SA 2.5
2011-03-28T14:06:24.980Z
2011-03-28T14:06:24.980Z
Ruub
<p>I think it is still open if Dominating Set or Hitting Set have a f(OPT) approximation for some (nontrivial) function f. This is should be a very difficult (and possible deep) question to answer. I consider it the most exciting question in parameterized approximation (along with the analogous question for Clique). You might want to have a look at my survey [1] that discusses this. Note that it is shown in the more recent paper [2] that "monotone circuit satisfiability for weft-2 circuits", a problem which is more general than Dominating Set, does not have f(OPT) approximation for any f.</p>

<p>[1] D. Marx. Parameterized complexity and approximation algorithms.
The Computer Journal, 51(1):60-78, 2008.</p>

<p>[2] D. Marx. Completely inapproximable monotone and antimonotone parameterized problems.
In Proceedings of the 25th Annual IEEE Conference on Computational Complexity, Cambridge, Massachusetts, 181-187, 2010.</p>

CC BY-SA 2.5
2011-03-30T12:00:08.603Z
Thanks for the references! This answers my question nicely.
Bart Jansen
CC BY-SA 2.5
2011-03-30T23:51:40.457Z
It may also be interesting to look at the following note of Nelson that shows that one cannot get good ratios that depend only m the number of sets. http://eccc.hpi-web.de/eccc-reports/2007/TR07-105/revisn01.pdf
Chandra Chekuri
CC BY-SA 2.5
2011-03-30T06:17:46.810Z
2011-03-30T06:17:46.810Z
Daniel Marx
<p>Consider the Dominating Set problem in general graphs, and let $n$ be the number of vertices in a graph. A greedy approximation algorithm gives an approximation guarantee of factor $1 + \log n$, i.e. it's possible to find in polynomial-time a solution $S$ such that $|S| \leq (1 + \log n) opt$, where $opt$ is the size of a minimum dominating set. There are bounds showing that we cannot improve the dependency on $\log n$ much <a href="http://www.cs.duke.edu/courses/spring07/cps296.2/papers/p634-feige.pdf">http://www.cs.duke.edu/courses/spring07/cps296.2/papers/p634-feige.pdf</a>.</p>

<p>My question: is there an approximation algorithm which has a guarantee in terms of $opt$ instead of $n$? In graphs where $n$ is very large with respect to the optimum, a factor-$\log n$ approximation would be much worse than a factor $\log opt$ approximation. Is something like that known, or are there reasons why this cannot exist? I am happy with any polynomial-time algorithm which produces a solution $S$ such that $|S| \in O(opt^c)$ for some constant $c$.</p>

<cc.complexity-theory><approximation-algorithms><approximation-hardness>
Existence of $opt^c$-approximation of Dominating Set with $c < 1$?
Bart Jansen
# Existence of $opt^c$-approximation of Dominating Set with $c < 1$?

(Asked by: username_0 on 2011-03-28)

Consider the Dominating Set problem in general graphs, and let $n$ be the number of vertices in a graph. A greedy approximation algorithm gives an approximation guarantee of factor $1 + \log n$, i.e. it's possible to find in polynomial-time a solution $S$ such that $|S| \leq (1 + \log n) opt$, where $opt$ is the size of a minimum dominating set. There are bounds showing that we cannot improve the dependency on $\log n$ much <http://www.cs.duke.edu/courses/spring07/cps296.2/papers/p634-feige.pdf>.

My question: is there an approximation algorithm which has a guarantee in terms of $opt$ instead of $n$? In graphs where $n$ is very large with respect to the optimum, a factor-$\log n$ approximation would be much worse than a factor $\log opt$ approximation. Is something like that known, or are there reasons why this cannot exist? I am happy with any polynomial-time algorithm which produces a solution $S$ such that $|S| \in O(opt^c)$ for some constant $c$.

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

---

## 2 answers

### Answer by username_2 on 2011-03-30. Score: 15 | Accepted answer

I think it is still open if Dominating Set or Hitting Set have a f(OPT) approximation for some (nontrivial) function f. This is should be a very difficult (and possible deep) question to answer. I consider it the most exciting question in parameterized approximation (along with the analogous question for Clique). You might want to have a look at my survey [1] that discusses this. Note that it is shown in the more recent paper [2] that "monotone circuit satisfiability for weft-2 circuits", a problem which is more general than Dominating Set, does not have f(OPT) approximation for any f.

[1] D. Marx. Parameterized complexity and approximation algorithms.
The Computer Journal, 51(1):60-78, 2008.

[2] D. Marx. Completely inapproximable monotone and antimonotone parameterized problems.
In Proceedings of the 25th Annual IEEE Conference on Computational Complexity, Cambridge, Massachusetts, 181-187, 2010.

> **Comments:**
> **username_0**: Thanks for the references! This answers my question nicely.  
> **username_3**: It may also be interesting to look at the following note of Nelson that shows that one cannot get good ratios that depend only m the number of sets. http://eccc.hpi-web.de/eccc-reports/2007/TR07-105/revisn01.pdf  

---

### Answer by username_1 on 2011-03-28. Score: 2

This should be a comment, since it does not directly answer your question, but a related question. Perhaps that a similar trick from [1] will provide you with an answer.

In [1] the following is proven:

Given a graph $G=(V,E)$ and a parameter $k$. There is no FPT algorithm (parameterized by $k$) that either: (a) returns an independent dominating set in $G$ of size at least $g(k)$, where $g(k)$ is a fixed function only depending on $k$ or (b) determines that $G$ does not have a dominating set of size $k$. (...Unless FPT = W[2].)

Any polynomial time algorithm that returns an independent dominating set of size at least $g(k)$, implies at least that FPT = W[2].

[1] Rodney G. Downey, Michael R. Fellows, Catherine McCartin and Frances Rosamond. "Parameterized Approximation of Dominating Set Problems". Information Processing Letters, Volume 109 Issue 1, December, 2008.

> **Comments:**
> **username_2**: The trick in [1] is based on the fact that Independent Dominating Set as a maximization problem is not monotone: a subset of a feasible solution is not necessarily a feasible solution (which is usually the case for maximization problems having meaningful approximations). Therefore, it is very well possible that every feasible solution has the same size, making approximation irrelevant.  

---

