Existence of $opt^c$-approximation of Dominating Set with $c < 1$?

Question

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

Answer 1

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.

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