8
$\begingroup$

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?

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ I'm guessing these graphs could have unbounded treewidth ? $\endgroup$ – Suresh Venkat May 29 '12 at 20:25
  • $\begingroup$ 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 (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. $\endgroup$ – Florent Foucaud May 30 '12 at 7:49
  • $\begingroup$ @SureshVenkat: As far as I understand the definition, complete graphs are undirected path graphs. So, they have unbounded treewidth. $\endgroup$ – Yoshio Okamoto May 30 '12 at 9:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.