Question

directed_steiner
hardness

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

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

1

Answers

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

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

where

A={r}×E{(e,S):eS}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.

1
Feedback