Minimum edge-weighted directed subgraph in polynomial time

Question

I am looking for an algorithm with polynomial complexity where, given a strongly connected edge-weighted digraph I can find the minimal subgraph which connects some root vertex v to a known set of other vertices.

As an example, given a strongly connected edge-weighted digraph with vertices labeled a-z, I want to find the minimal subgraph rooted at node j that includes nodes b, f, g, and p.

In my case I am going to be using this to determine an optimal pipeline for doing image manipulation (I already have a strongly connected edge-weighted digraph for this application).

Answer 1

This is an instance of the Directed Steiner Network Problem and as such it's solvable in time $|V(G)|^{O(|T|)}$ as proved by Feldman & Ruhl (2006), where $G$ is the given graph and $T\subset V(G)$ is the given subset of vertices (terminals).

Answer 2

If you don't want to implement a specialized algorithm, you can solve the problem via mixed integer linear programming as follows. Let $T$ be the set of terminal nodes. For each directed arc $(i,j)\in A$, let nonnegative variable $x_{ij}$ be the flow from $i$ to $j$, and let binary variable $y_{ij}$ indicate whether arc $(i,j)$ is used. The problem is to minimize $$\sum_{(i,j)\in A} c_{ij} y_{ij}$$ subject to \begin{align} \sum_{(i,j)\in A} x_{ij} - \sum_{(j,i)\in A} x_{ji} &= \begin{cases} |T| &\text{if $i=v$} \\ -1 &\text{if $i\in T$} \\ 0 &\text{otherwise} \end{cases} \\ x_{ij} &\le |T|y_{ij} \end{align}