<p>Too bad you have been waiting so long without getting any answer.
I don't know for the classes you asked for, but I know some related graph classes and new techniques you can try.</p>

<p>First I will mention that <a href="http://www.cs.utoronto.ca/~chaplick/" rel="nofollow">Steven Chaplick</a> has done work on related graph classes, he finished his thesis earlier this year, you might find his research interesting.</p>

<p>I know some results in this direction follow from my own work
<a href="http://www.ii.uib.no/~martinv/Papers/Logarithmic_booleanwidth.pdf" rel="nofollow">Graph Classes with Structured Neighbourhoods and Algorithmic Applications</a>
This gives a general technique for solving various problems including DSP in certain graph classes. 
We do this by introducing new graph decompositions (see my <a href="http://www.ii.uib.no/~martinv/Papers/MartinThesis.pdf" rel="nofollow">thesis</a>).</p>

<p>For instance if we are give an intersection model of UP where the tree has max degree d and the paths have max length s we can solve dominating set in $(d-1)^{3(s-1)}poly(n)$.</p>

<p>Similar if we have a graph given with an intersection model consisting of $0$-bend paths in a $k \times n$ grid (for constant k).</p>

<p>The same technique might work for CEPT arising form a host tree of maximum degree 3, but I need some more time to understand this class.
If you have a link to some characterizations of this class that would help.</p>

CC BY-SA 3.0
2012-11-30T13:50:05.350Z
Thanks for your answer, Martin. In fact I have been aware of your work on boolean width (Gabriel Renault, who is a colleague here, pointed it out to me) and I have tried this approach about a year ago, without success. My graphs, I think, can have linear boolean-width: if I remember well, they are more or less intersection graphs of paths of a comb graph (a path graph + one pendant vertex per initial vertex), with the endpoints of all paths being degree-1-vertices. But I should definitely take a look at your work.
Florent Foucaud
CC BY-SA 3.0
2012-11-23T16:56:21.407Z
2012-11-23T16:56:21.407Z
Martin Vatshelle
<p>I am interested in the complexity of the dominating set problem (DSP) in some specific graph classes which are subclasses of <a href="http://en.wikipedia.org/wiki/Chordal_graph">chordal graphs</a>.</p>

<p>A graph is an <a href="http://www.graphclasses.org/classes/gc_129.html">undirected path graph</a> if it is the vertex-intersection graph of a family of paths in some undirected tree. Let UP be the class of undirected path graphs.</p>

<p>A graph is an <a href="http://www.graphclasses.org/classes/gc_128.html">EPT graph</a> if it is the edge-intersection graph of a family of paths in some undirected tree. An EPT graph may not be chordal, but let CEPT be the class of chordal EPT graphs.</p>

<p>A graph is a <a href="http://www.graphclasses.org/classes/gc_175.html">(rooted) directed path graph</a> if it is the vertex-intersection graph of a family of directed paths in some rooted directed tree (i.e. all arcs directed away from the root). Let RDP be the class of (rooted) directed path graphs.</p>

<p>We have $RDP\subseteq CEPT \subseteq UP\subseteq chordal$ </p>

<p>It is known that the DSP is linear-time solvable for graphs in RDP but NP-complete for graphs of UP [<a href="http://epubs.siam.org/sicomp/resource/1/smjcat/v11/i1/p191_s1">Booth and Johnson, 1981</a>]</p>

<p>I am interested in special graphs which correspond to vertex-intersection graphs of families of undirected paths in caterpillar-like trees of maximum degree 3.
More precisely, these "caterpillars" are built from a path in which each second vertex has a pendant degree-one-vertex attached to.
Let us call this class cat-UP.</p>

<p>Moreover, my special graphs can also be constructed as the edge-intersection graphs of some families of undirected paths in specific trees of maximum degree 3.</p>

<p>So my questions are:</p>

<p>1) Is the complexity of the DSP for graphs of cat-UP known ?
(note that the reduction in [<a href="http://epubs.siam.org/sicomp/resource/1/smjcat/v11/i1/p191_s1">Booth and Johnson, 1981</a>] produces a host tree which is of maximum degree 3, but quite far from a caterpillar)</p>

<p>2) What is the complexity of DSP for graphs of CEPT ? And for graphs of CEPT arising form a host tree of maximum degree 3 ?
(<a href="http://www.graphclasses.org/classes/gc_127.html">this is not known to ISGCI</a>)</p>

<p>3) Is there any complexity result for the DSP in a closely related graph family ?</p>

CC BY-SA 3.0
2012-01-21T01:20:36.680Z
I love your question on complexity for the DSP here. Interested in what comes from this
Gabriel Fair
<reference-request><graph-theory><graph-algorithms><np-hardness>
The complexity of the dominating set problem in specific subclasses of chordal graphs
Florent Foucaud
# The complexity of the dominating set problem in specific subclasses of chordal graphs

(Asked by: username_0 on 2012-01-19)

I am interested in the complexity of the dominating set problem (DSP) in some specific graph classes which are subclasses of [chordal graphs](http://en.wikipedia.org/wiki/Chordal_graph).

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. Let UP be the class of undirected path graphs.

A graph is an [EPT graph](http://www.graphclasses.org/classes/gc_128.html) if it is the edge-intersection graph of a family of paths in some undirected tree. An EPT graph may not be chordal, but let CEPT be the class of chordal EPT graphs.

A graph is a [(rooted) directed path graph](http://www.graphclasses.org/classes/gc_175.html) if it is the vertex-intersection graph of a family of directed paths in some rooted directed tree (i.e. all arcs directed away from the root). Let RDP be the class of (rooted) directed path graphs.

We have $RDP\subseteq CEPT \subseteq UP\subseteq chordal$

It is known that the DSP is linear-time solvable for graphs in RDP but NP-complete for graphs of UP [[Booth and Johnson, 1981](http://epubs.siam.org/sicomp/resource/1/smjcat/v11/i1/p191_s1)]

I am interested in special graphs which correspond to vertex-intersection graphs of families of undirected paths in caterpillar-like trees of maximum degree 3.
More precisely, these "caterpillars" are built from a path in which each second vertex has a pendant degree-one-vertex attached to.
Let us call this class cat-UP.

Moreover, my special graphs can also be constructed as the edge-intersection graphs of some families of undirected paths in specific trees of maximum degree 3.

So my questions are:

1) Is the complexity of the DSP for graphs of cat-UP known ?
(note that the reduction in [[Booth and Johnson, 1981](http://epubs.siam.org/sicomp/resource/1/smjcat/v11/i1/p191_s1)] produces a host tree which is of maximum degree 3, but quite far from a caterpillar)

2) What is the complexity of DSP for graphs of CEPT ? And for graphs of CEPT arising form a host tree of maximum degree 3 ?
([this is not known to ISGCI](http://www.graphclasses.org/classes/gc_127.html))

3) Is there any complexity result for the DSP in a closely related graph family ?

**Tags:** reference-request, graph-theory, graph-algorithms, np-hardness

> **Comments:**
> **username_1**: I love your question on complexity for the DSP here. Interested in what comes from this  

---

## 1 answers

### Answer by username_2 on 2012-11-23. Score: 4

Too bad you have been waiting so long without getting any answer.
I don't know for the classes you asked for, but I know some related graph classes and new techniques you can try.

First I will mention that [Steven Chaplick](http://www.cs.utoronto.ca/~chaplick/) has done work on related graph classes, he finished his thesis earlier this year, you might find his research interesting.

I know some results in this direction follow from my own work
[Graph Classes with Structured Neighbourhoods and Algorithmic Applications](http://www.ii.uib.no/~martinv/Papers/Logarithmic_booleanwidth.pdf)
This gives a general technique for solving various problems including DSP in certain graph classes.
We do this by introducing new graph decompositions (see my [thesis](http://www.ii.uib.no/~martinv/Papers/MartinThesis.pdf)).

For instance if we are give an intersection model of UP where the tree has max degree d and the paths have max length s we can solve dominating set in $(d-1)^{3(s-1)}poly(n)$.

Similar if we have a graph given with an intersection model consisting of $0$-bend paths in a $k \times n$ grid (for constant k).

The same technique might work for CEPT arising form a host tree of maximum degree 3, but I need some more time to understand this class.
If you have a link to some characterizations of this class that would help.

> **Comments:**
> **username_0**: Thanks for your answer, Martin. In fact I have been aware of your work on boolean width (Gabriel Renault, who is a colleague here, pointed it out to me) and I have tried this approach about a year ago, without success. My graphs, I think, can have linear boolean-width: if I remember well, they are more or less intersection graphs of paths of a comb graph (a path graph + one pendant vertex per initial vertex), with the endpoints of all paths being degree-1-vertices. But I should definitely take a look at your work.  

---

