4
The best approximation ratio that can be achieved in polynomial time should be $\Theta(\log n)$ where $n$ is the number of vertices. This can be seen by standard reductions from the Set Cover problem which is NP-hard to approximate within a factor of $(1-\alpha)\cdot N$ where $N$ is the input size [1].
First, we use the standard reduction from Set Cover to ...
2
In this answer i assume that $u$ is an ancestor of $v$ if $u$ can reach $v$ by a directed path.
This is basically as hard as Set Cover (Given family $F$ over a universe $U$, find smallest subfamily $F’$ of $F$ whose union is $U$). To reduce from Set Cover:
Make a vertex for every set in $F$ and for every element in $U$. Make an arc from every element to ...
Only top voted, non community-wiki answers of a minimum length are eligible
