EDIT: the answer is WRONG. I made the (silly) implicit assumption that when a path-flow starts at time s and ends at time t and goes through edge e, it blocks edge e for this duration. However, this is not true. See *.
Note: Perhaps this approach is needlessly complicated or incorrect. Although I did try to verify, and write it down carefully - I did not spend huge amounts of time on it.
Assuming `stockpiling' is not allowed e.g. the flow has to be transfered immediately. Let $m$ denote the number of edges and $N$ the input length. I did not specify continuous or discrete time, since I did not take it into consideration. It should work for discrete thought, for continuous I'm note sure.
Then, we can describe the solution as a set of "paths-flows" from source to sink. A path-flow is a quadruple $(P,s,a,r)$ which consists of the following: A simple path $P$ from source to sink; Starting time of the path-flow $s$; Amount of flow through the path $a$; Throughput rate $r$.
Let a solution be given by a set $F$ of path-flows. We can verify whether the solution given by these path-flows is correct in time polynomial in $|F|$ and $N$:
- For every edge $e$ and a moment of time $t$, add up the throughput rate of all path-flows going over $e$ at time $t$. Every path-flow has a start and end time, therefore we only need to consider the moments of time when a path-flow starts or ends (between these moments nothing changes with regard to the path-flows that go over edge $e$.
- For every path-flow we can verify whether all it's flow arrives at the sink before time $T$.
- For every edge we can verify whether a path-flow goes through after it has been destroyed or not.
- The lower bound of flow $B$ we can simply check, by adding up the amounts of flow of the flow-paths.
Now, we 'just' need to show that the number of path-flows is polynomial in $N$.
For a given solution we can determine the time some flow passed an edge and when the edge was destroyed. Convert this to a problem with an equivalent solution: there are hard bounds on each edge when it can be used and when not - a start and end time. Let $\{t_1,...,t_k\}$ denote the set of all these times.
Consider some non-compact solution and (initially) an empty set of path-flows. The idea is that we iteratively find a path-flow in the non-compact solution, remove it and store it in our set of path-flows.
Find path-flows that start and end between $t_i$ and $t_j$, $i<j$ but do not end between any $t_p$ and $t_q$ such that $[t_p,t_q] \subseteq [t_i,t_j]$. Let $F_{i,j}$ denote the set of path-flows between $t_j$ and $t_j$ with the properties as described above.
Assume that we already have removed all path-flows for all smaller intervals than $[i,j]$. Greedily find path-flows that start and end in $[t_i,t_j]$. When we find one, remove this flow from the solution and adjust the throughput rates of vertices accordingly and the amount of flow send from the source to sink as well. For this path-flow we maximize the throughput. This means that for at least one edge we have reached it's maximum throughput rate or after removing this path-flow there is no more flow over this edge. Note that this holds for the period $[t_{i+1},t_{j-1}]$.
In both cases, no more flow goes through this edge and we can conclude that $|F_{s,t}| \leq m$.
(*) Why is the previous claim true? Well, every other path flow in $F_{t_i,t_j}$ starts before $t_{i+1}$ and ends after $t_{j-1}$. Therefore, the must overlap in time that they use a certain edge. Since the throughput is maximized for the path-flow, there must be an edge where it is tight.
From this follows that $\sum_{i,j \in [k]} | F_{i,j} |\leq c m^3 $ for some constant $c$ and the claim that it's in NP follows.
