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 ?

  • $\begingroup$ I love your question on complexity for the DSP here. Interested in what comes from this $\endgroup$ Jan 21, 2012 at 1:20

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

  • $\begingroup$ 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. $\endgroup$ Nov 30, 2012 at 13:50

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.