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


2 Answers 2


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.


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.

  • 1
    $\begingroup$ 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. $\endgroup$ Mar 30, 2011 at 5:59

Your Answer

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

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