# 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.

• 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 Jan 20 '11 at 10:11
• 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 Jan 20 '11 at 11:03
• 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 Jan 21 '11 at 11:57
• 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 Jan 21 '11 at 11:59
• @daveagp: Did you try PSPACE-hardness, for example reducing QBF to your problem? – Yoshio Okamoto Jan 22 '11 at 0:10

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"

• "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 Nov 25 '12 at 19:06
• 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 Nov 26 '12 at 21:43
• 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 Dec 2 '12 at 4:43

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.

• 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 Jan 25 '11 at 21:59
• 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 Jan 26 '11 at 8:54

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).

• I cannot understand what your claim is. – Tsuyoshi Ito Jan 25 '11 at 3:06
• 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 Jan 25 '11 at 3:48
• 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 Jan 25 '11 at 22:03
• @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. Jan 26 '11 at 17:34
• @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. Jan 26 '11 at 17:38