Approximating the dominating set on a certain kind of DAG
That problem is hard to approximate by reduction from set cover:

max(DTM) = 2 ​ ​ ​ and ​ ​ ​ exactly one vertex has ​ DTM = 0​

and ​ ​ ​ the vertices with ​ DTM = 1 ​ are exactly the sets ​ ​ ​ and

the vertices with ​ DTM = 2 ​ are exactly the set-elements

To push a solution forward, just add in the ​ DTM = 0 ​ vertex.

To pull a solution back, remove that vertex if it's present, and for each

DTM = 2 ​ vertex, replace that vertex with any one of the sets that element is in.

However, you presumably have another property: ​ low maximum degree .

That is useful because:

Your problem is a special case of set cover: ​ The elements are the vertices and the

sets are those formed as [v in V such that u=v or (u,v) in E] for elements u of V.

The size of those sets is bounded above by one plus your graph's maximum out-degree.

Theorem 3.1.6 says the greedy algorithm does significantly better on such instances.