We consider the Directed Steiner Network problem, also called the Point-to-Point Connection problem, where given a directed graph G and p pairs { (s₁,t₁), ..., (s_p,t_p) } of nodes in the graph, one has to find the smallest subgraph H of G that contains paths from s_i to t_i for all i. The problem is NP-hard for general p, since the Directed Steiner Tree problem is a special case. Until now, the complexity was unknown for constant p >= 3.

We prove that the problem is polynomially solvable if p is any constant number, even if nodes and edges in G are weighted and the goal is to minimize the total weight of the subgraph H.

In addition, we give an efficient algorithm for the Strongly Connected Steiner Subgraph problem for any constant p, where given a directed graph and p nodes in the graph, one has to compute the smallest strongly connected subgraph containing the p nodes.