### Question

In the *directed Steiner tree problem*, we are given as input a directed graph $G = (V, A)$, non-negative costs $c_{ij} \geq 0$ for arcs $(i, j) \in A$, a root vertex $r \in V$, and a set of terminals $T \subseteq V$. The goal is to find a minimum-cost tree such that for each $i \in T$ there exists a directed path from $r$ to $i$.

Prove that for some constant $c$ there can be no $c\log |T|$-approximation algorithm for the directed Steiner tree problem, unless P = NP.

### Answers

We will show an approximation preserving reduction from the Set Cover problem. Given a set of elements $E$ and a set of subsets $\mathcal{S} \subseteq 2^E$ we will contract the following directed Steiner tree instance:

$G = (\{r\} \cup E \cup \mathcal{S}, A)$

where

$A = \{r\} \times E \cup \{(e, S) : e \in S\}$

It is easy to verify that every Steiner tree is corresponded to a set cover of the same cost and vice versa.