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

• The number of outgoing edges follows roughly an exponential distribution. Does that affect the value of the approximation? – FUZxxl Feb 13 '17 at 22:27
• That should give you a better direct lower-bound on the optimum size (the sum of set sizes needs to be at least the number of vertices), which should let you get a better bound from Theorem ​ 3.1.5 . ​ ​ ​ ​ – user12859 Feb 13 '17 at 22:31