<p>The best approximation ratio that can be achieved in polynomial time should be <span class="math-container">$\Theta(\log n)$</span> where <span class="math-container">$n$</span> is the number of vertices. This can be seen by standard reductions from the <em>Set Cover</em> problem which is NP-hard to approximate within a factor of <span class="math-container">$(1-\alpha)\cdot N$</span> where <span class="math-container">$N$</span> is the input size [<a href="https://doi.org/10.4086/toc.2015.v011a007" rel="nofollow noreferrer">1</a>].</p>
<p>First, we use the standard reduction from <em>Set Cover</em> to <em>Red Blue Dominating Set</em>: Build a bipartite graph with a red and a blue side. The red side corresponds to the sets of the Set Cover instance and the blue side corresponds to the elements of the universe and an edge connects a set <span class="math-container">$S$</span> and an element <span class="math-container">$e$</span> if <span class="math-container">$S$</span> contains <span class="math-container">$e$</span>. Now selecting a set of red vertices to dominate all blue vertices is the same as selecting the sets of the Set Cover instance to cover the universe. Hence, the reduction is approximation-preserving.</p>
<p>The bipartite graph is of course not chordal and we have a coloring of the vertices but we can now make the red side a clique and forget the vertex colors. We will never select a formerly blue vertex since the red vertices have larger neighborhoods. The resulting graph is a split graph and thus also a chordal graph.</p>
<p><a href="https://doi.org/10.4086/toc.2015.v011a007" rel="nofollow noreferrer">Dana Moshkovitz: The Projection Games Conjecture and the NP-Hardness of <span class="math-container">$\ln n$</span>-Approximating Set-Cover. Theory Comput. 11: 221-235 (2015)</a></p>

CC BY-SA 4.0
2020-10-16T17:55:11.587Z
2020-10-16T17:55:11.587Z
Christian Komusiewicz
<p>I am searching results and papers related to the (in)approximability of the Minimum Dominating Set problem in chordal graphs. In particular, what is the best approximation ratio achievable in polytime here ?</p>
<p>The problem was shown to be <span class="math-container">$W[1]$</span>-hard for the natural parametrization by Liu and Song in 2009.</p>

<graph-algorithms><approximation-algorithms><approximation-hardness>
Best approximations of Minimum Dominating Sets in chordal graphs
Mathieu Mari
# Best approximations of Minimum Dominating Sets in chordal graphs

(Asked by: username_0 on 2020-10-16)

I am searching results and papers related to the (in)approximability of the Minimum Dominating Set problem in chordal graphs. In particular, what is the best approximation ratio achievable in polytime here ?

The problem was shown to be $W[1]$-hard for the natural parametrization by Liu and Song in 2009.

**Tags:** graph-algorithms, approximation-algorithms, approximation-hardness


---

## 1 answers

### Answer by username_1 on 2020-10-16. Score: 4 | Accepted answer

The best approximation ratio that can be achieved in polynomial time should be $\Theta(\log n)$ where $n$ is the number of vertices. This can be seen by standard reductions from the *Set Cover* problem which is NP-hard to approximate within a factor of $(1-\alpha)\cdot N$ where $N$ is the input size [[1](https://doi.org/10.4086/toc.2015.v011a007)].

First, we use the standard reduction from *Set Cover* to *Red Blue Dominating Set*: Build a bipartite graph with a red and a blue side. The red side corresponds to the sets of the Set Cover instance and the blue side corresponds to the elements of the universe and an edge connects a set $S$ and an element $e$ if $S$ contains $e$. Now selecting a set of red vertices to dominate all blue vertices is the same as selecting the sets of the Set Cover instance to cover the universe. Hence, the reduction is approximation-preserving.

The bipartite graph is of course not chordal and we have a coloring of the vertices but we can now make the red side a clique and forget the vertex colors. We will never select a formerly blue vertex since the red vertices have larger neighborhoods. The resulting graph is a split graph and thus also a chordal graph.

[Dana Moshkovitz: The Projection Games Conjecture and the NP-Hardness of $\ln n$-Approximating Set-Cover. Theory Comput. 11: 221-235 (2015)](https://doi.org/10.4086/toc.2015.v011a007)


---

