Best approximations of Minimum Dominating Sets in chordal graphs 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.
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].
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)