<p>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.</p>

<ul>
<li><a href="http://en.wikipedia.org/wiki/Line_graph" rel="noreferrer">http://en.wikipedia.org/wiki/Line_graph</a></li>
<li><a href="http://en.wikipedia.org/wiki/Edge_dominating_set" rel="noreferrer">http://en.wikipedia.org/wiki/Edge_dominating_set</a></li>
</ul>

CC BY-SA 3.0
2011-08-10T14:22:06.127Z
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
CC BY-SA 3.0
2011-08-11T03:48:19.677Z
@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
CC BY-SA 3.0
2011-08-10T01:46:02.943Z
2011-08-10T01:46:02.943Z
Yoshio Okamoto
<p>In graph excluding a fixed minor e.g. planar graphs, many problems, including vertex cover, <strong>dominating set</strong>, 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. </p>

<p><a href="http://erikdemaine.org/papers/BidimensionalSurvey_CJ/paper.pdf" rel="nofollow">The Bidimensionality Theory and
Its Algorithmic Applications</a></p>

CC BY-SA 3.0
2011-08-09T22:12:24.937Z
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
CC BY-SA 3.0
2011-08-10T14:19:20.233Z
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
CC BY-SA 3.0
2011-08-09T20:11:11.957Z
2011-08-09T20:39:11.640Z
2011-08-09T20:39:11.640Z
Thang Dinh
<p>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.</p>

<p>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 <a href="http://www.sciencedirect.com/science/article/pii/S0890540108000928" rel="nofollow">here, Lemma 1</a> for a proof of, in particular, the first inequality).</p>

CC BY-SA 3.0
2012-05-29T12:25:48.623Z
2012-05-29T12:25:48.623Z
Florent Foucaud
<p>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: </p>

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

<p>Thanks in advance.
Kind regards.</p>

CC BY-SA 3.0
2011-08-09T19:41:49.263Z
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
CC BY-SA 3.0
2011-08-10T14:14:57.960Z
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
<graph-theory><graph-algorithms><approximation-algorithms>
Approximation algorithms for dominating set problem
user2582
# Approximation algorithms for dominating set problem

(Asked by: username_0 on 2011-08-09)

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.

**Tags:** graph-theory, graph-algorithms, approximation-algorithms
> **Comments:**
> **username_1**: 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?  
> **username_0**: 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.  

---

## 3 answers

### Answer by username_2 on 2011-08-10. Score: 9

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.

* <http://en.wikipedia.org/wiki/Line_graph>
* <http://en.wikipedia.org/wiki/Edge_dominating_set>

> **Comments:**
> **username_0**: 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.  
> **username_2**: @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)?  

---

### Answer by username_3 on 2011-08-09. Score: 5

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](http://erikdemaine.org/papers/BidimensionalSurvey_CJ/paper.pdf)

> **Comments:**
> **username_4**: 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.  
> **username_0**: 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.  

---

### Answer by username_5 on 2012-05-29. Score: 1

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](http://www.sciencedirect.com/science/article/pii/S0890540108000928) for a proof of, in particular, the first inequality).


---

