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