Maximum flow with minimal number of vertices used

Question

In many of the research problems I encountered recently, the following version of the minimum cost maximum flow problem came up. We are given a directed graph $D$, a source vertex $s$ and a terminal vertex $t$, and for each edge we have an integer capacity $c(e)$. We want to find an (integral) flow of maximum value that minimizes the number of vertices $v$, such that there is a positive inflow to $v$. This starts to look more and more NP-hard, but I still have hope it is solvable. Have this problem been studied anywhere? It certainly seems like a problem of great interest.

Answer 1

Actually, it turns out to be NP complete. We can easily reduce from X3C, by adding an edge with capacity 3 from a source to each set and an edge with capacity one from each element to the terminal. Also orient each edge between the sets and elements towards the elements. These also have capacity one. Then, there is a flow of value $3n$ using only $4n$ vertices if and only if there is an exact 3cover.