Polynomial Integrality Gap of Flow LP for Directed Steiner Tree

In the Directed Steiner Tree (DST) problem, we are given a directed graph on vertices with edge-costs , a root vertex , and a set of terminals. The goal is to find a minimum-cost subgraph of that contains a path from to every terminal . DST has been a notorious problem for decades as there is a large gap between the best-known polynomial-time approximation ratio of for any constant , and the best quasi-polynomial-time approximation ratio of {formula present.} Toward understanding this gap, we study the integrality gap of the standard flow linear programming relaxation for the problem. We show that the linear program (LP) has an integrality gap of . Previously, the integrality gap of the LP is only known to be {formula present.} [Halperin et al., SODA'03 & SIAM J. Comput.] and [Zosin-Khuller, SODA'02] in some instance with {formula present.}. Our result gives the first known lower bound on the integrality gap of this standard LP that is polynomial in , the number of vertices. Consequently, we rule out the possibility of developing a poly-logarithmic approximation algorithm for the problem based on the flow LP relaxation.