1
$\begingroup$

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?)

$\endgroup$
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The number of outgoing edges follows roughly an exponential distribution. Does that affect the value of the approximation? $\endgroup$ – FUZxxl Feb 13 '17 at 22:27
  • $\begingroup$ 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 . ​ ​ ​ ​ $\endgroup$ – user12859 Feb 13 '17 at 22:31

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.