1
$\begingroup$

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.

$\endgroup$

1 Answer 1

4
$\begingroup$

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)

$\endgroup$

Your Answer

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

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