<p>I am interested in the complexity of the minimum dominating set problem (MDSP) in some specific graph class.</p>

<p>A graph is an <a href="http://www.graphclasses.org/classes/gc_129.html" rel="nofollow">undirected path graph</a> 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 <a href="http://epubs.siam.org/sicomp/resource/1/smjcat/v11/i1/p191_s1" rel="nofollow">here</a>). My question is:</p>

<blockquote>
  <p>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?</p>
</blockquote>

<p>Notes:<br>
1) I could not find a reference for this question, including in <a href="http://books.google.fr/books/about/Domination_in_Graphs.html?id=iBFrQgAACAAJ&amp;redir_esc=y" rel="nofollow">this standard textbook about domination</a>, where Chapter 8 is devoted to the complexity of the (decision problem) dominating set.<br>
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 <a href="http://www.sciencedirect.com/science/article/pii/S0890540108000928" rel="nofollow">here</a>).<br>
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?</p>

CC BY-SA 3.0
2012-05-29T20:25:15.197Z
I'm guessing these graphs could have unbounded treewidth ?
Suresh Venkat
CC BY-SA 3.0
2012-05-30T07:49:19.413Z
Well, if they had treewidth, say, at most k, the MDSP would be solvable in polynomial time [i.e. f(k).poly(G)] by Courcelle's theorem, but as mentioned it is NP-hard. In fact, if I understood the discussion in this paper (http://arxiv.org/abs/1009.0216) on different width parameters well (Corollary 4.3), even unit interval graphs (a subclass of undirected path graphs) already have unbounded treewidth/cliquewidth/rankwidth.
Florent Foucaud
CC BY-SA 3.0
2012-05-30T09:05:08.100Z
@SureshVenkat: As far as I understand the definition, complete graphs are undirected path graphs. So, they have unbounded treewidth.
Yoshio Okamoto
<ds.algorithms><reference-request><graph-theory><approximation-algorithms><approximation-hardness>
Is the dominating set problem constant-factor-approximable in undirected path graphs?
Florent Foucaud
# Is the dominating set problem constant-factor-approximable in undirected path graphs?

(Asked by: username_0 on 2012-05-29)

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](http://www.graphclasses.org/classes/gc_129.html) 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](http://epubs.siam.org/sicomp/resource/1/smjcat/v11/i1/p191_s1)). 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](http://books.google.fr/books/about/Domination_in_Graphs.html?id=iBFrQgAACAAJ&redir_esc=y), 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](http://www.sciencedirect.com/science/article/pii/S0890540108000928)).  
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?

**Tags:** ds.algorithms, reference-request, graph-theory, approximation-algorithms, approximation-hardness
> **Comments:**
> **username_1**: I'm guessing these graphs could have unbounded treewidth ?  
> **username_0**: Well, if they had treewidth, say, at most k, the MDSP would be solvable in polynomial time [i.e. f(k).poly(G)] by Courcelle's theorem, but as mentioned it is NP-hard. In fact, if I understood the discussion in this paper (http://arxiv.org/abs/1009.0216) on different width parameters well (Corollary 4.3), even unit interval graphs (a subclass of undirected path graphs) already have unbounded treewidth/cliquewidth/rankwidth.  
> **username_2**: @SureshVenkat: As far as I understand the definition, complete graphs are undirected path graphs. So, they have unbounded treewidth.  

---

## 0 answers

