Approximating the dominating set on a certain kind of DAG A dominating set on a directed graph $G=(V,E)$ is a subset $D$ of $V$ such that for all $v\in V$ it holds that $v\in D$ or there is an $u\in D$ such that  $(u,v)\in E.$

For a concrete problem (size reduction of endgame tablebases), I want to approximate the dominating set of a directed acyclic graph with the following properties:


Each vertex $v\in V$ has a nonnegative integer $\mathop{\mathrm{DTM}}(v)$ assigned to it (with DTM standing for distance to mate)
For each pair of vertices $(u,v)$, if $(u,v)\in E$, then $1+\mathop{\mathrm{DTM}}(u)=\mathop{\mathrm{DTM}}(v)$ (if a move leads from $v$ to $u$, then the distance to mate from $v$ is one larger than that from $u$)
For each vertex $v\in V,$ there exists a vertex $z\in V$ with $\mathop{\mathrm{DTM}}(z)=0$ such that a path from $z$ to $v$ exists (each position can be brought to mate)


Given these boundary conditions, is there an efficient way to approximate $D$ for large graphs (more than 100'000'000 nodes?)
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.