Super Mario Flows in NP? One classical extension of the max-flow problem is the "max-flow over time" problem: you are given a digraph, two nodes of which are distinguished as the source and the sink, where each arc has two parameters, a capacity-per-unit-time and a delay. You are also given a time horizon $T$. The goal is to compute a flow over time which gets the maximum amount of material from the source to the sink by time $T$. A flow of maximum value can be computed in polynomial time by a clever classical reduction to min-cost max-flow.

I am interested in an extension to this model where edges have a third "life-span" parameter. If an arc has life-span $\ell$, and $t$ is the earliest time at which positive flow is sent through the arc, then we destroy the arc at time $t+\ell$. You can think of this as like the platforms in Super Mario Brothers which fall away/are destroyed shortly after you step on them, or you can think of them as batteries needed to power the edges, which cannot be turned off after they are turned on. (Edit:) The decision problem is, when also given a flow value lower bound $B$, whether one can schedule a flow meeting both the time horizon upper bound and flow value lower bound.

So far I can see that this problem is strongly NP-hard (via 3-partition). But, I do not actually know if it is in NP: is there any guarantee of a way to express a solution compactly? In the classical version, some special type of optimal flow is used to circumvent this problem.

Note: the model above is a little underspecified, since you may allow or disallow the stockpiling of flow at nodes, and you may have a discrete time model or a continuous one. Resolving the question for any of these models would be excellent.
It's been a long time but I am pretty sure this problem is in P.

I wrote my PhD dissertation about this in 1995. See "Efficient Dynamic Network flow algorithms" by Bruce Hoppe submitted to Cornell CS dept. Online at http://dspace.library.cornell.edu/bitstream/1813/7181/1/95-1524.pdf

See Chapter 8 "Extensions" section 8.1 about "mortal edges"