I am interested in the complexity of the minimum dominating set problem (MDSP) in some specific graph class.A graph is an undirected path graph if it is the vertex-intersection graph of a family of paths in some undirected tree (this is a subclass of chordal graphs). It is known that the MDSP is NP-hard when considering undirected path graphs (see here). My question is:What is known about the (in)approximability of the MDSP in undirected path graphs? In particular, is there a constant-factor (polynomial-time) approximation algorithm for this problem?Notes:1) I could not find a reference for this question, including in this standard textbook about domination, where Chapter 8 is devoted to the complexity of the (decision problem) dominating set.2) It is NP-hard to approximate the MDSP within $o(log(n))$ in another subclass of chordal graphs, split graphs. This follows from an easy reduction from minimum set cover (see here).3) I think the original NP-hardness reduction for undirected path graphs from the above reference can be used to show that the MDSP admits no PTAS in this class of graphs. But would this be tight?
Is the dominating set problem constant-factor-approximable in undirected path graphs?
ds.algorithms;reference request;graph theory;approximation algorithms;approximation hardness