The complexity of the dominating set problem in specific subclasses of chordal graphs

Question

I am interested in the complexity of the dominating set problem (DSP) in some specific graph classes which are subclasses of chordal graphs.

A graph is an undirected path graph 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 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 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]

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] 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)

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

Answer 1

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 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 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).

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.