Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

2 Answers

up vote 14 down vote accepted

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.

share|improve this answer
    
Thanks for the references! This answers my question nicely. –  Bart Jansen Mar 30 '11 at 12:00
    
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. eccc.hpi-web.de/eccc-reports/2007/TR07-105/revisn01.pdf –  Chandra Chekuri Mar 30 '11 at 23:51
add comment

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.

share|improve this answer
1  
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 Mar 30 '11 at 5:59
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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