# Approximation algorithms for dominating set problem

I am working on approximation algorithms for minimum dominating set problem. In particular, I am interested in graphs classes restricted by forbidden induced subgraphs. Since the domination problem and its variants have been extensively studied, I suppose someone may worked on this before. So, the question is:

Does someone knows papers where it is studied approximation algorithms for domination problem for graphs classes defined by forbidden induced subgraphs?

• The general dominating set problem is equivalent (even in the approximate version) to set-cover, for which the greedy algorithm is optimal. I wonder - if you forbid induced subgraphs of the kinds that interest you, does it correspond to something natural for set-cover? – Dana Moshkovitz Aug 9 '11 at 19:41
• Thanks. I don't know what you mean with "natural" but I couldn't found anything useful by looking for "set-cover" approximations. For example, graphs without diamonds doesn't seem to have a natural relationship with set-cover, but maybe I am not seeing it. – user2582 Aug 10 '11 at 14:14

The class of line graphs can be characterized by a finite family of forbidden induced subgraphs (Beineke). A dominating set in a line graph G corresponds to an edge dominating set of the root graph of G (and vice versa), and the size of minimum edge dominating set can be approximated by factor of 2 in polynomial time.

• Thanks. It is an useful answer. However I was looking for some work where I could see an analysis of approximation algorithms on graphs, based on their definition by forbidden induced subgraphs. I am trying to figure out if there are results useful for my work or in other case ideas that I could use before starting to reinventing the wheel. – user2582 Aug 10 '11 at 14:22
• @user2582: Would you make it more specific what you mean by "based on their definition by forbidden induced subgraphs"? Do you also allow a family of forbidden induced subgraphs to be infinite (for example, as bipartite graphs, which forbid all odd cycles as induced subgraphs)? – Yoshio Okamoto Aug 11 '11 at 3:48

In graph excluding a fixed minor e.g. planar graphs, many problems, including vertex cover, dominating set, edge dominating set, R-dominating set, connected dominating set, connected edge dominating set can be well-approximated (often PTAS or within constant factors). The following paper can serve as a starting point.

The Bidimensionality Theory and Its Algorithmic Applications

• Forbidding a minor is much more restrictive than forbidding an induced subgraph. I would assume that these results do not carry over to the case of forbidden induced subgraphs. – James King Aug 9 '11 at 22:12
• I saw this paper before posting my question, and is very interesting but it just doesn't fit to what I was looking for. It gives results for more restrictive graphs (minor-free), like James King said. – user2582 Aug 10 '11 at 14:19

In the same flavour as the answer by Y. Okamoto, there is an easy argument showing that the dominating set problem admits an $(\ell-1)$-approximation algorithm in induced $K_{1,\ell}$-free graphs.

Indeed, just take any independent dominating set $I$ (i.e. a maximal independent set): we have the chain of inequalities $\frac{\alpha(G)}{\ell-1}\leq \gamma(G)\leq I\leq\alpha(G)$, where $\gamma(G)$ and $\alpha(G)$ are the domination number and independence number of $G$, respectively (see here, Lemma 1 for a proof of, in particular, the first inequality).