9
$\begingroup$

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?

Thanks in advance. Kind regards.

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ 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? $\endgroup$
    – Dana Moshkovitz
    Aug 9, 2011 at 19:41
  • $\begingroup$ 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. $\endgroup$
    – user2582
    Aug 10, 2011 at 14:14

3 Answers 3

Reset to default
9
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – user2582
    Aug 10, 2011 at 14:22
  • $\begingroup$ @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)? $\endgroup$
    – Yoshio Okamoto
    Aug 11, 2011 at 3:48
5
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – James King
    Aug 9, 2011 at 22:12
  • $\begingroup$ 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. $\endgroup$
    – user2582
    Aug 10, 2011 at 14:19
1
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

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

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