<p>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 *. </p>

<p>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.</p>

<p>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.</p>

<p>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$.</p>

<p>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$:</p>

<ul>
<li>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$.</li>
<li>For every path-flow we can verify whether all it's flow arrives at the sink before time $T$.</li>
<li>For every edge we can verify whether a path-flow goes through after it has been destroyed or not.</li>
<li>The lower bound of flow $B$ we can simply check, by adding up the amounts of flow of the flow-paths.</li>
</ul>

<p>Now, we 'just' need to show that the number of path-flows is polynomial in $N$.</p>

<p>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.</p>

<p>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. </p>

<p>Find path-flows that start and end between $t_i$ and $t_j$, $i&lt;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. </p>

<p>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$.</p>

<p>(*) 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.</p>

<p>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.</p>

CC BY-SA 2.5
2011-01-25T21:59:21.887Z
To me the decomposition bound looks faulty, I'll try to give an illustrative counterexample. Suppose the network is just one source->sink edge of capacity 100, delay 0, lifespan 100. Now consider this flow schedule: in time interval [0, 1) send flow at a rate of 1; in [1, 2) at a rate of 2, etc up to rate 100 in [99, 100). Any decomposition needs >=100 paths-flows which contradicts your claim as I understand it. I should mention that Ford and Fulkerson avoid this obstacle in their classical solution (without life-spans) by considering a specific type of optimal solution, not an arbitrary one.
daveagp
CC BY-SA 2.5
2011-01-26T08:54:10.147Z
This can probably be avoided by also maximizing the 'lifespan' of the flow, but there is another problem in the proof, I've editted it to make it clear.
Ruub
CC BY-SA 2.5
2011-01-25T15:47:51.247Z
2011-01-26T08:58:02.297Z
2011-01-26T08:58:02.297Z
Ruub
<p>The way I understand it, you would need to store only one number per arc, representing the instant at which flow begins to be sent through the arc. That is assuming that after that, the arc is rendered unusable. If, otherwise, the arc can be used again after it stops being used, it should have solutions arbitrarily close to solutions to maximum flow over time (since the flow could stop being sent for an arbitrarily small amount of time and then start being pumped again).</p>

CC BY-SA 2.5
2011-01-25T03:06:10.617Z
I cannot understand what your claim is.
Tsuyoshi Ito
CC BY-SA 2.5
2011-01-25T03:48:41.530Z
I don't think this is correct.  For example, imagine a network with three nodes, the source s, the terminal t, and another node v, with three arcs a1 = (s,v), a2 = (s,v), a3 = (v,t).  Capacities of the arcs are all 1, and the traveling times are set to be 0 for a1 and a3, and 100 for a2.  The life-spans are 1 for a1, and 1000 for a2 and a3.  Then, at time 0 one can send one unit of flow through a1 and a3 from s to t, and starts sending one unit of flow through a2.  During time 1 to 99, a3 carries no flow, since a1 is gone, but at time 100, flow through a2 arrives at v, and a3 is used again.
Yoshio Okamoto
CC BY-SA 2.5
2011-01-25T22:03:16.280Z
If I understand correctly, you claim in part that once the birth/death times of the edges are fixed, the remaining problem can be solved using the classical max-flow over time approach, but I do not see how this is the case.
daveagp
CC BY-SA 2.5
2011-01-26T17:34:49.147Z
@Yoshio: In that case, if, instead of beginning to send one unit of flow along a2 immediately, you stopped sending flows altogether, after an arbitrarily short amount of time a1 could be used once more, and that would yield a better solution.
Leandro M.
CC BY-SA 2.5
2011-01-26T17:38:40.187Z
@Dave: no, that's not exactly what I claim. What I'm saying is that either each arc can be used only a finite number of times, or the solutions to the problem should arbitrarily approximate the solutions to max-flow-over-time. I am concerned about the details of the problem definition, in short.
Leandro M.
CC BY-SA 2.5
2011-01-27T07:18:13.340Z
I feel Leandro misunderstood the definition of a lifespan.  Leandro seems to see the lifespan of an arc as the total duration in which the arc carries a positive amount of flow.  For example, if we have an arc from s to t with delay 0 and lifespan 2, and we send a unit of flow through the arc at time 0 and stop sending at time 1, then Leandro's definition (as far as I feel) doesn't destroy the arc at time 2 (since the arc has carried flow only for 1 unit of time), but daveagp's definition destroys the arc at time 2 (since the arc was used at time 0 for the first time).
Yoshio Okamoto
CC BY-SA 2.5
2011-01-27T22:06:11.097Z
No, I am using exactly the same definition. The problem is: it is not specified what happens to the arc when it disappears. Either it can be used again at a future time (in which case you can have solutions that are arbitrarily close to max-flow-over-time) or it cannot (in which case only the starting time for each arc is needed to describe a solution).
Leandro M.
CC BY-SA 2.5
2011-01-28T01:43:30.617Z
@Leandro: Thanks for the clarification.  I understand your concern.  I've assumed the latter implicitly.
Yoshio Okamoto
CC BY-SA 2.5
2011-01-25T02:33:08.023Z
2011-01-25T02:33:08.023Z
Leandro M.
<p>It's been a long time but I am pretty sure this problem is in P.</p>

<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 <a href="http://dspace.library.cornell.edu/bitstream/1813/7181/1/95-1524.pdf">http://dspace.library.cornell.edu/bitstream/1813/7181/1/95-1524.pdf</a></p>

<p>See Chapter 8 "Extensions" section 8.1 about "mortal edges"</p>

CC BY-SA 3.0
2012-11-25T19:06:23.953Z
*"It was a dark and stormy night.  Jack lay motionless in his cabin -- motionless except for his stomach, which was gyrating in his gut like a mad carnival ride..."* (page xiii, where the author discusses practical applications).
Neal Young
CC BY-SA 3.0
2012-11-26T21:43:09.263Z
Nice quote, Neal! :)  BTW daveagp makes a good point about needing pseudo-polynomial space to store the "flow" that answers the decision question. How to not only find optimal flow but also represent that flow in P is chapters 1-7 of my dissertation
Bruce Hoppe
CC BY-SA 3.0
2012-12-02T04:43:10.697Z
Excellent! I finally read all this. Once we fix the first time flow hits an edge, proving feasibility of the network with resulting start and end times is in P (assuming holdover's allowed), and therefore the original problem is in NP: our polynomial-sized certificate lists the start time for each edge. Super Mario therefore flows NP-completely. Random questions: does forbidding holdover change anything? is there a decent approximation algorithm?
daveagp
CC BY-SA 3.0
2012-11-25T11:39:00.330Z
2012-11-25T11:39:00.330Z
Bruce Hoppe
<p>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.</p>

<p>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. (<em>Edit</em>:) 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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2011-01-20T10:11:22.440Z
I'm not sure I understand. Why is there a problem in expressing a particular flow plan compactly and verifying that the total flow is at least F in poly time ?
Suresh Venkat
CC BY-SA 2.5
2011-01-20T11:03:05.080Z
You may be thinking of how to prove that the output of an optimization problem, whose output is a timed flow, can be checked for optimality in poly time.  However, often one shows that decision problems with only yes/no answers are in NP, and optimization problems that maximize some function like flow are typically turned into a decision problem by adding a lower bound value B to the input, and the decision problem becomes "Is there a solution with value at least B?"
andy_fingerhut
CC BY-SA 2.5
2011-01-21T11:57:51.837Z
Suresh: say in the discrete model, the natural way to express a flow plan takes $T$ integers for each arc, but this is not polynomial, it is only pseudo-polynomial in the input size. In the continuous model similarly I don't see how to compress this.
daveagp
CC BY-SA 2.5
2011-01-21T11:59:09.540Z
Andy: You are correct, in formal terms it is better for me to state this as a decision problem by having a value lower bound in addition to a time horizon, then it is something for which we could ask if it lies in NP.
daveagp
CC BY-SA 2.5
2011-01-22T00:10:39.993Z
@daveagp: Did you try PSPACE-hardness, for example reducing QBF to your problem?
Yoshio Okamoto
<ds.algorithms><graph-algorithms><network-modeling><max-flow-min-cut>
Super Mario Flows in NP?
daveagp
# Super Mario Flows in NP?

(Asked by: username_0 on 2011-01-20)

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.

**Tags:** ds.algorithms, graph-algorithms, network-modeling, max-flow-min-cut

> **Comments:**
> **username_1**: I'm not sure I understand. Why is there a problem in expressing a particular flow plan compactly and verifying that the total flow is at least F in poly time ?  
> **username_2**: You may be thinking of how to prove that the output of an optimization problem, whose output is a timed flow, can be checked for optimality in poly time.  However, often one shows that decision problems with only yes/no answers are in NP, and optimization problems that maximize some function like flow are typically turned into a decision problem by adding a lower bound value B to the input, and the decision problem becomes "Is there a solution with value at least B?"  
> **username_0**: Suresh: say in the discrete model, the natural way to express a flow plan takes $T$ integers for each arc, but this is not polynomial, it is only pseudo-polynomial in the input size. In the continuous model similarly I don't see how to compress this.  
> **username_0**: Andy: You are correct, in formal terms it is better for me to state this as a decision problem by having a value lower bound in addition to a time horizon, then it is something for which we could ask if it lies in NP.  
> **username_3**: @username_0: Did you try PSPACE-hardness, for example reducing QBF to your problem?  

---

## 3 answers

### Answer by username_7 on 2012-11-25. Score: 13 | Accepted answer

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 username_7 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"

> **Comments:**
> **username_8**: *"It was a dark and stormy night.  Jack lay motionless in his cabin -- motionless except for his stomach, which was gyrating in his gut like a mad carnival ride..."* (page xiii, where the author discusses practical applications).  
> **username_7**: Nice quote, Neal! :)  BTW username_0 makes a good point about needing pseudo-polynomial space to store the "flow" that answers the decision question. How to not only find optimal flow but also represent that flow in P is chapters 1-7 of my dissertation  
> **username_0**: Excellent! I finally read all this. Once we fix the first time flow hits an edge, proving feasibility of the network with resulting start and end times is in P (assuming holdover's allowed), and therefore the original problem is in NP: our polynomial-sized certificate lists the start time for each edge. Super Mario therefore flows NP-completely. Random questions: does forbidding holdover change anything? is there a decent approximation algorithm?  

---

### Answer by username_4 on 2011-01-25. Score: 2

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

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.

> **Comments:**
> **username_0**: To me the decomposition bound looks faulty, I'll try to give an illustrative counterexample. Suppose the network is just one source->sink edge of capacity 100, delay 0, lifespan 100. Now consider this flow schedule: in time interval [0, 1) send flow at a rate of 1; in [1, 2) at a rate of 2, etc up to rate 100 in [99, 100). Any decomposition needs >=100 paths-flows which contradicts your claim as I understand it. I should mention that Ford and Fulkerson avoid this obstacle in their classical solution (without life-spans) by considering a specific type of optimal solution, not an arbitrary one.  
> **username_4**: This can probably be avoided by also maximizing the 'lifespan' of the flow, but there is another problem in the proof, I've editted it to make it clear.  

---

### Answer by username_5 on 2011-01-25. Score: 1

The way I understand it, you would need to store only one number per arc, representing the instant at which flow begins to be sent through the arc. That is assuming that after that, the arc is rendered unusable. If, otherwise, the arc can be used again after it stops being used, it should have solutions arbitrarily close to solutions to maximum flow over time (since the flow could stop being sent for an arbitrarily small amount of time and then start being pumped again).

> **Comments:**
> **username_6**: I cannot understand what your claim is.  
> **username_3**: I don't think this is correct.  For example, imagine a network with three nodes, the source s, the terminal t, and another node v, with three arcs a1 = (s,v), a2 = (s,v), a3 = (v,t).  Capacities of the arcs are all 1, and the traveling times are set to be 0 for a1 and a3, and 100 for a2.  The life-spans are 1 for a1, and 1000 for a2 and a3.  Then, at time 0 one can send one unit of flow through a1 and a3 from s to t, and starts sending one unit of flow through a2.  During time 1 to 99, a3 carries no flow, since a1 is gone, but at time 100, flow through a2 arrives at v, and a3 is used again.  
> **username_0**: If I understand correctly, you claim in part that once the birth/death times of the edges are fixed, the remaining problem can be solved using the classical max-flow over time approach, but I do not see how this is the case.  
> **username_5**: @Yoshio: In that case, if, instead of beginning to send one unit of flow along a2 immediately, you stopped sending flows altogether, after an arbitrarily short amount of time a1 could be used once more, and that would yield a better solution.  
> **username_5**: @Dave: no, that's not exactly what I claim. What I'm saying is that either each arc can be used only a finite number of times, or the solutions to the problem should arbitrarily approximate the solutions to max-flow-over-time. I am concerned about the details of the problem definition, in short.  
> **username_3**: I feel Leandro misunderstood the definition of a lifespan.  Leandro seems to see the lifespan of an arc as the total duration in which the arc carries a positive amount of flow.  For example, if we have an arc from s to t with delay 0 and lifespan 2, and we send a unit of flow through the arc at time 0 and stop sending at time 1, then Leandro's definition (as far as I feel) doesn't destroy the arc at time 2 (since the arc has carried flow only for 1 unit of time), but username_0's definition destroys the arc at time 2 (since the arc was used at time 0 for the first time).  
> **username_5**: No, I am using exactly the same definition. The problem is: it is not specified what happens to the arc when it disappears. Either it can be used again at a future time (in which case you can have solutions that are arbitrarily close to max-flow-over-time) or it cannot (in which case only the starting time for each arc is needed to describe a solution).  
> **username_3**: @Leandro: Thanks for the clarification.  I understand your concern.  I've assumed the latter implicitly.  

---

