{'fraction_non_alphanumeric': 0.06038278371821368, 'fraction_numerical': 0.013388444604187259, 'mean_word_length': 3.737902653611466, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On the Min-Max-Delay Problem: NP-completeness, Algorithm, and Int-Gap

We study a flow problem where a source streams information to a sink over a directed graph G=(V;E) possibly using multiple paths to minimize the maximum end-to-end delay, denoted as Min-Max-Delay problem. Different from the maximum latency problem, our setting is unique in that communication over an edge incurs a constant delay within an associated capacity. We prove that Min-Max-Delay is weakly NP-complete, and demonstrate that it becomes strongly NP-complete if we require integer flow solution. We propose an optimal pseudo-polynomial time algorithm for Min-Max-Delay. Moreover, we propose a fully polynomial time approximation scheme. Besides, in this paper we observe that the optimal Min-Max-Delay flow can only be achieved by fractional flow solution in some problem instances and in the worst case the Int-Gap, which is defined as the maximum delay gap between the optimal integer Min-Max-Delay flow and the optimal Min-Max-Delay flow, can be infinitely large. We also propose a near-tight bi-criteria bound for the Int-Gap. In the end, we show how the results introduced in this paper can be extended to the multi-commodity Min-Max-Delay problem case.


I. INTRODUCTION
Delay-sensitive network flows have strong applications in many domains, including communication networks, cyberphysical systems, transportation networks and evacuation planning [1]. In communication networks like video conferencing, the video delivery delay shall be no more than 250ms to ensure a good interactive conferencing experience [2]. In cyber-physical systems, shorter delay for control messages can improve control quality [3]. In transportation networks, timely delivery is critical to deliver perishable goods [4]. In evacuation planning, it is important to move all people from hazardous areas to safe areas as soon as possible [5].
There are mainly two different flow models for delaysensitive flow problems: the flow-amount model and the flowrate model. The flow-amount model is suitable to the applications where the flow is generated once, e.g., people to be moved in the evacuation planning, while the flow-rate model is suitable to the applications where the flow is generated continuously, e.g., the video streaming in video conferencing. For both models, two key delay-sensitive network flow problems either maximize the flow (amount or rate) subject to a maximum delay constraint or minimize the maximum delay subject to a flow (amount or rate) requirement. We summarize related studies in Tab. I. Max-flow subject to delay constraint Min-max delay subject to flow requirement Flow-amount Model [6], [10] [7], [11] Flow-rate Model [8], [12] [9], [13], our paper For the flow-amount model, the first problem, called dynamic flow problem [6], is to maximize the flow amount to be delivered from a source to a sink within a given time horizon. [6] showed that it can be formulated as a min-cost flow problem and thus solved in polynomial time by various min-cost flow algorithms. The second problem, called quickest flow problem, is to minimize the time horizon to deliver a given amount of flow from a source to a sink and is also solvable in polynomial time [7].
For the flow-rate model, the first problem, called delayconstrained max-flow problem [8], is to maximize the flow rate to be sent from a source to a sink while the end-toend delay is bounded above by a given delay constraint. The problem has been proved to be NP-complete [8]. The second problem, called maximum latency problem [9], is to minimize the maximum end-to-end delay that flow units experience from a source to a sink while satisfying a given flow rate requirement and has been proved to be NP-complete [9].
Compared with the maximum latency problem, this work targets a similar but different problem, denoted as Min-Max-Delay. Specifically, there are two key differences from the assumption of non-negative, non-decreasing and differentiable flow-dependent edge delay functions in the maximum latency problem [9], [13]: (i) Each edge has a capacity constraint such that assigned flow rate cannot exceed the given capacity; (ii) Edge transmission delay is a constant within the capacity and goes to infinity otherwise. Existing results on the maximum latency problem including the complexity analysis and approximation algorithms [9], [13] are not applicable to our work due to the two key differences. Our work has many applications. For example, in transportation network, the ground vehicle speed (or equivalently the time to pass the road) remains nearly constant before reaching a certain flow rate [14], [15].
In this paper, we make the following contributions: We prove that Min-Max-Delay is weakly NP-complete in Thm. IV-B based on the results in Sec. III-A and Sec. IV. In Thm. 2 of Sec. III-B we prove Min-Max-Delay becomes strongly NP-complete if each path can only have an integer flow.
In Sec. IV, we propose a simple binary-search algorithm, which can find the optimal solution to Min-Max-Delay in pseudo-polynomial time. The time complexity of the algorithm is O(log(N d max )(N 5 d 2.5 max )(log R + N 2 d max log(N 2 d max ))), where N max{|V |, |E|}, R is the rate requirement, and d max is the maximum edge delay. The complexity is pseudopolynomial because it is polynomial in the numeric value of the input, i.e., d max in our problem, but is exponential in the bit length of the input, i.e., log(d max ) [16].
In Sec. V, we propose a Fully Polynomial Time Approximation Scheme (FPTAS) to the Min-Max-Delay. The time complexity is O((L + log N ) log(M )(N M 2.5 (log R + N M log(N M ))) where M = |E|(1 + 1/ ) + 1 and L is the bit complexity for representing d max .
In Sec. VI, we give examples to show that the Int-Gap, which is defined as the maximum delay gap between the Min-Max-Delay flow and the optimal integer Min-Max-Delay flow, can be infinitely large. Moreover, a near tight bi-criteria bound of (1 − , 1/ ) is then introduced for the Int-Gap.
In the end of this work, we show how to extend previous proposed results in this paper to the multi-commodity Min-Max-Delay case.

II. SYSTEM MODEL AND PROBLEM FORMULATION
We consider a network modeled as a directed graph G (V, E) with |V | nodes and |E| edges. Each edge e ∈ E has a non-negative integer capacity c e and a non-negative integer delay d e . We define N max{|V |, |E|} and d max max e∈E d e as the maximal edge delay over all edges. A source node s ∈ V needs to send a positive integer rate R to a sink node t ∈ V \{s}.
We denote P as the set of all paths from s to t. For any path p ∈ P , we denote its path delay as d p e∈E:e∈p d e . A flow solution f is defined as the assigned flow rate over P , i.e., f {x p : x p ≥ 0, p ∈ P }. For a flow solution f , we define x e p∈P :e∈p x p as the flow rate on edge e ∈ E. We further define the maximum delay of a flow solution f as i.e., the maximum delay among paths that carry positive rates. We consider the problem of finding a flow solution f to minimize the maximum delay M(f ) while satisfying both the flow rate requirement and edge capacity constraints. We denote the problem as Min-Max-Delay. It is formulated as x e = p∈P :e∈p where (2a) together with (2d) define our objective which is to minimize the maximum path delay for s − t paths that carry positive flow rates (called flow-carrying paths). In fact, M(f ) = M in the formulation (2). (2b) restricts that the source s sends R rate to the sink t, and (2c) requires that the flow rate on edge e does not exceed its capacity c e . We use f MM (R) to denote the optimal solution to the problem 2, namely the Min-Max-Delay flow given rate requirement R. Formulation (2) is a convex optimization problem [17]. However, there exists a key difficulty to solve Min-Max-Delay from formulation (2): the number of paths (number of variables) could exponentially increase with respect to the input network size.
The integer Min-Max-Delay problem, denoted as Int-Min-Max-Delay, further requires that each path carries an integer flow rate, i.e., replacing (2e) by vars. x p ∈ Z + , ∀p ∈ P. ( Different from Min-Max-Delay flow which minimizes the maximum delay, another well-known delay-aware network flow in the literature is the system-optimal flow, which is defined as follows: Definition 1 (System-optimal flow). The system-optimal flow minimizes the total delay of the flow over all edges: The flow is feasible in the sense that it meets the capacity constraint, flow conservation constraint, non-negative constraint as well as the rate requirement.
Integer system-optimal flow is the integer flow that minimizes total delay. Given a rate requirement R, we denote the system-optimal flow as f SO (R) and the integer system-optimal flow as f SO + (R).

III. HARDNESS RESULTS
In Sec. III-A, we prove that Min-Max-Delay is NPcomplete based on the reduction from the NP-complete partition problem [16]. In Sec. III-B, we further prove that Int-Min-Max-Delay is NP-complete in the strong sense based on the pseudo-polynomial transformation from the classic strongly NP-complete 3-partition problem [16].

A. NP-completeness for Min-Max-Delay
We first define partition and the partition problem below.
Definition 2 (Partition). Given a non-empty set A, its partition is a set of non-empty subsets such that each element in A is in exactly one of these subsets.
Definition 3 (Partition Problem [16]). Given a set of n positive integers A = {a 1 , a 2 , ..., a n } with sum ai∈A a i = 2b. Is there a partition {A 1 , A 2 } of A such that ai∈A1 a i = aj ∈A2 a j = b?
The partition problem is known to be NP-complete [16] (in the weak sense). We now leverage it to prove that Min-Max-Delay is NP-complete. Theorem 1. The decision version of Min-Max-Delay problem is NP-complete.
Proof: For any partition problem with set A = {a 1 , a 2 , ..., a n } and b where any a i ∈ A is a positive integer and ai∈A = 2b, we construct a graph G with (2n + 1) nodes and 3n edges as in Fig. 1. All edges in the graph have a capacity of 1. Each edge (w i−1 , w i ) (denoted as dashed lines in the figure) has a delay of a i for all i = 1, · · · , n, and all edges (w i−1 , v i ) and (v i , w i ) (denoted as solid lines in the figure) have a delay of zero. Obviously it takes polynomial time to construct the graph G given any partition problem. We then consider the following decision problem of Min-Max-Delay: for graph G with source s = w 0 , sink t = w n , and flow rate requirement R = 2, is there any feasible flow f such that the maximum delay M(f ) ≤ b?
Now we prove the partition problem answers "Yes" if and only if the decision version of Min-Max-Delay answers "Yes".
If Part. If the decision problem of Min-Max-Delay answers "Yes", then there exists a flow f such that the maximum delay M(f ) ≤ b. Since f is feasible, the total rate from w 0 to w n in f is R = 2. Now due to the capacity constraint and flow conservation, all edges must exactly have a flow rate 1 to satisfy the requirement R = 2. The total delay in flow f is p∈P Also, because the total flow rate is equal to 2, it is x p = 2b. (6) As both ends in (6) are the same, it must be Therefore, all flow-carrying paths have a path delay of b. We choose an arbitrary flow-carrying path p. Since all solid edges have a delay of 0, the path delay of p is the delay of all dashed edges that belongs to p. We consider the set A 1 that contains a i if edge (w i−1 , w i ) ∈ p. Clearly, it holds that ai∈A1 a i = b. We then define A 2 = A\A 1 . It shall be aj ∈A2 = a k ∈A − ai∈A1 = 2b − b = b. A 1 and A 2 are thus a partition of set A and meet the requirement of the partition problem. Hence, the partition problem answers "Yes".
Only If Part. If the partition problem answers "Yes", then there exists a partition A 1 and A 2 such that ai∈A1 a i = aj ∈A2 a j = b. We now construct two paths p 1 and p 2 . Due to the definition of a partition (see Definition 2), A 1 and A 2 are two disjoint sets, i.e., A 1 ∩ A 2 = ∅. Thus, we can easily see that p 1 and p 2 are two disjoint s − t paths, i.e., p 1 and p 2 do not share any common edge. We can see that d p1 = ai∈A1 = b, and d p2 = ai∈A2 = b. We then construct the flow f with only two flow-carrying paths p 1 and p 2 and set x p1 = x p2 = 1. Since p 1 and p 2 are disjoint, the capacity constraint is satisfied. Also, since x p1 + x p2 = R = 2, the rate requirement is satisfied. Thus f is a feasible flow with maximum delay M(f ) = b. Therefore, the decision problem of Min-Max-Delay answers "Yes".
Since the partition problem is NP-complete [16] and the reduction can be done in polynomial time, the decision problem of Min-Max-Delay is also NP-complete.

B. Strongly NP-completeness for Int-Min-Max-Delay
If we further require that any path flow should be an integer, the corresponding flow problem becomes harder. In this subsection, we show that Int-Min-Max-Delay is NPcomplete in the strong sense, based on the pseudo-polynomial transformation from the 3-Partition Problem [16]. [16]). Given a set of n = 3k (k > 0) positive integers A = {a 1 , a 2 , ..., a n } with sum

Definition 4 (3-Partition Problem
The 3-partition problem has been proved to be NP-complete in the strong sense in [16]. We now leverage it to show our Int-Min-Max-Delay problem is NP-complete in the strong sense. Consider the following decision version for Int-Min-Max-Delay: for graph G with source s = w 0 , sink t = w n , and flow rate requirement R = k, is there any feasible integer flow f with maximum delay M(f ) ≤ b?
If Part. If the decision problem of Int-Min-Max-Delay answers "Yes", then there exists a feasible integer flow f with maximal delay M(f ) ≤ b. For any flow-carrying path p in f , the flow rate x p must be a positive integer and since all edges have unit capacity, the flow rate f p must be 1. For a feasible integer flow, due to p∈P :x p >0 x p = R = k, there must exist exactly k flow-carrying paths. In addition, all k flow-carrying paths are disjoint in the sense that no edge will appear in two or more flow-carrying paths, because otherwise the edge capacity constraint will be violated.
Similar to the If Part in the proof of Thm. 1, we can show that the flow rate of all edges is 1 and all flow-carrying paths have a path delay of b.
Let us index all k flow-carrying paths by p 1 , p 2 , · · · , p k . We can construct k sets A 1 , A 2 , · · · , A k as follows: for i ∈ [1, n], since the flow rate of edge (w i−1 , w i ) is 1, there must exists a path p j containing edge (w i−1 , w i ), and then we put a i into set A j . Since all paths are disjoint, we can easily see that {A 1 , A 2 , · · · , A k } is a partition of set A. In addition, since any p j has a path delay of b, we also have ai∈Aj a i = b for any set A j . Therefore, the 3-partition problem answers "Yes".
Only If Part. If the 3-partition problem answers "Yes", then there exists a partition Similar to the Only If Part in the proof of Thm. 1, we can show that the decision problem of Int-Min-Max-Delay also answers "Yes".
As the 3-partition problem is strongly NP-complete and our reduction is a pseudo-polynomial transformation, the decision version of Int-Min-Max-Delay is also strongly NP-complete.

IV. OPTIMAL PSEUDO-POLYNOMIAL TIME ALGORITHM
This section describes a pseudo-polynomial time algorithm which can find the optimal solution to the Min-Max-Delay problem. The algorithm runs in pseudo-polynomial time in the sense that corresponding time complexity in theory is polynomial w.r.t. the numerical value of the largest edge delay.

A. Related work
A closely-related problem to Min-Max-Delay is the Delay-Constrained maximum flow problem [12], denoted as DC-Max-Flow: for the same graph G and a given delay constraint T , find the maximum flow (rate) such that the delay of any flow-carrying path does not exceed T . Let us denote P T as the set of all s − t paths whose path delay does not exceed T . Then DC-Max-Flow can be formulated as vars.
Since the size of set P T increases exponentially with respect to the network size, formulation (8) could have exponential number of variables. However, [12] shows that DC-Max-Flow can be solved with an edge-based flow formulation which has at most |E|T variables. They implicitly use the idea of expanding graph in the time range [18] by converting a delay-constrained max-flow problem in the original graph into a delay-unconstrained max-flow problem over the expanded graph. In [12], the authors only consider unit-delay edges, but it is straightforward to generalize their results to integerdelay edges. Due to the space limit, we omit the procedure of constructing the expanded graph and directly give the equivalent edge-based flow formulation for DC-Max-Flow as follows [12,Proposition 1], e is the total flow rate that experiences a delay of d after passing edge e from the source s. The objective (9a) is the total flow rate that arrives at the sink t within the delay bound T . Eqs. (9b) are the flow conservation constraints in the expanded graph. Note that by convention, for any edge e ∈ E, we set x

B. Proposed binary-search algorithm
We now show the relationship between our problem Min-Max-Delay and the problem DC-Max-Flow. For a graph G, denote d * (R) as the minimal maximum delay with rate requirement R (the optimal value of Min-Max-Delay). For the same graph G and a non-negative integer T , denote r * (T ) as the maximum flow subject to a delay constraint T (the optimal value of DC-Max-Flow). We have the following lemma. Lemma 1 suggests a simple binary-search algorithm to solve Min-Max-Delay optimally. Given a lower bound T l (= 0 initially) and an upper bound T u (= |E|d max initially) of the optimal maximum delay, in each iteration we solve the problem (9) with T = (T l + T u )/2 . We compare the optimal value of (9), i.e., r * (T ) with the rate requirement R. If r * (T ) ≥ R, we update the upper bound as T u = T . Otherwise, if r * (T ) < R, we update the lower bound as T l = T + 1. The algorithm terminates when T l ≥ T u . Lemma 1 clearly show that such a binary-search algorithm finds the optimal solution of Min-Max-Delay. We then present its time complexity. Proof: Our binary search scheme terminates in O(log T ) iterations where T = |E|d max is the initial upper bound for the minimal maximum delay. In each iteration, we need to solve the linear program (9). Obviously the number of variables in (9) is O(|E|T ). The conservation constraint (9b) is formulated for v ∈ V \{s, t} and d ∈ [0, T ]. Thus the number of conservation constraint is O(|V |T ). Clearly the number of capacity constraint (9c) is |E|. Overall, the number of constraints in formulation (9) is O(N T ).
[19] has proposed an algorithm to solve a linear program within time O((g + h) 1.5 hL) where g is the number of constraints, h is the number of variables, and L denotes the standard "bit complexity" of the linear program. Therefore, it takes O((N T ) 2.5 (log R + N T log(N T ))) time to solve formulation (9) based on the calculation of L [20] and the Hadamard's inequality. Since T ≤ |E|d max , the overall time complexity is O(log(N d max )(N 5 d 2.5 max )(log R +N 2 d max log(N 2 d max ))). A direct result of Thm. 3 is as follows. A. Related work [13] has proposed the system-optimal flow which minimizes the total delay to be a γ(L)-approximate solution for the general Min-Max-Delay problem where edge delay is a nonnegative, non-decreasing convex function w.r.t the assigned flow rate and no capacity constraints are involved in the problem. For the constant edge delay function, calculated γ(L) is 1, leading to an algorithm (the algorithm that calculates the system-optimal flow) with the optimal solution guaranteed. However, it is a totally different story when edge capacity constraints are involved which is the problem setting in this paper.
In fact, with capacity constraints involved, the maximum delay gap between the system-optimal flow and the Min-Max-Delay flow can be infinitely large. Use Fig. 4 as an example. Suppose R = (n − 1)/(n − 2) > 1. In this example, the maximum delay of the Min-Max-Delay flow is 1 according to Lem. 7. For the system-optimal flow, it will place 1 flow rate on each lower edge and 1/(n−2) flow rate on each upper edge. Then the system-optimal flow that only uses two paths, one containing all upper dashed edges and one containing all lower solid edges, will have a maximum delay of n − 1. Thus, the maximum delay gap between the system-optimal flow and the Min-Max-Delay flow in this example is n − 1 and can be infinitely large as n increases.
Overall, existed approximate algorithm is not applicable for the Min-Max-Delay problem introduced in this paper. Proof. Suppose P f is the flow-carrying path set of f . Since the only difference between G andĜ is the edge delay, P f is same for the flow f in G and inĜ.  return f (R) 15: end procedure Algorithm 2 is our proposed FPTAS to solve Min-Max-Delay, which is a simple binary search procedure on the Test(·) described in Algorithm 1. Note that we use T * (line 11) to denote the input T to get f (R) using Test(·).

B. Proposed FPTAS
Lemma 5. In the end of Algorithm 2, it holds that T * ≤ M(f MM (R)).
Proof. Obviously initially T U = |E| · d max is an upper bound for M(f MM (R)) since the number of edges on any flowcarrying paths can be assumed to be bounded above by |E| in f MM (R) without loss of generality.
It is clear that if we can prove Test(G, s, t, R, T, ) must return a feasible flow for any T ≥ M(f MM (R)), Lem. 5 will hold since Algorithm 2 is a binary search procedure on Test(·). According to Lem. 3 obviously it is true that a feasible flow must be returned for any T ≥ M(f MM (R)). Therefore, Lem. 5 is correct.
Theorem 5. Algorithm 2 is a (1 + )-approximate algorithm for the Min-Max-Delay problem, namely Proof.  N M log(N M )))). Due to the binary search procedure, we need at most O(log(|E|d max )) iterations. Therefore, overall we can get the proposed time complexity.

VI. FRACTIONAL FLOW VS. INTEGER FLOW
We have shown that Min-Max-Delay, which allows fractional path flows, is NP-complete in the weak sense, but Int-Min-Max-Delay, which only allows integer path flows, is NP-complete in the strong sense. This section further presents another key difference: the optimum of Min-Max-Delay, namely the maximum delay of the Min-Max-Delay flow, may be better than the optimum of Int-Min-Max-Delay, namely the maximum delay of the Int-Min-Max-Delay flow.
A famous integral flow theorem holds for the classic maxflow problem: there must exist an optimal integral flow if each edge has integral capacity [10]. However, when edge delay is involved, Min-Max-Delay does not have similar integral flow theorems in spite of the integral capacity, delay, and flow rate requirement, namely the Min-Max-Delay flow must be fractional in some problem instances. Here in this paper we define the Int-Gap as the maximum delay ratio between the Int-Min-Max-Delay flow and Min-Max-Delay flow which maybe fractional. A. A simple example with Int-Gap = 9/8 In Fig. 3, we use the nice example from [12, Fig. 2] as a building block. We place two such blocks (v-related block and w-related block) side by side disjointly and then connect them to a source s and a sink t. The capacity of edges (s, v 1 ), (s, w 1 ), (v 6 , t) as well as (w 6 , t) is 2 and the capacity a 1 a 2 a 3 a n-1 a n ... of all other edges is 1. We set the delay to be 1 for all edges and the rate requirement to be 3.
For the subnetwork from v 1 to v 6 (and its symmetric subnetwork from w 1 to w 6 ), there are totally 5 different paths (shown in Tab. II). For the DC-Max-Flow problem shown in [12], given a maximum delay constraint of 6, the subnetwork has a fractional maximum flow of 1.5: x B = 0.5, x D = 0.5 and x E = 0.5, while the integer maximum flow is 1 due to capacity constraint. Since in Fig. 3 the symmetric vrelated subnetwork and w-related subnetwork are placed side by side, given R = 3 in our Min-Max-Delay problem, the optimal flow will route 1.5 flow rate to each of the subnetwork, resulting in a maximum delay of 8. However, for Int-Min-Max-Delay, one of the subnetworks shall have a flow rate of 2, and the corresponding maximum delay is 9. Therefore, the optimal fractional flow solution could be better (i.e., with smaller maximum delay) than the optimal integral solution. There are two useful lemmas for the network shown in Fig. 4 where source is a 1 and sink is a n . Proof. Because of the unit capacity constraint for each edge, any flow-carrying path will be assigned a unit flow rate in the integer flow from a 1 to a n .
Because of the rate requirement R = 2, there are exactly two flow-carrying paths in the Int-Min-Max-Delay flow and each of them carries a unit flow rate.
Moreover, because of the capacity constraint, the two flowcarrying paths are disjoint, namely they share no edges.
Therefore, since the Int-Min-Max-Delay flow minimizes the maximum flow-carrying path delay among all integer flows, the two flow-carrying paths will have path delay of (n−1)/2 and (n − 1)/2 respectively in the Int-Min-Max-Delay flow, leading to a maximum delay of (n − 1)/2 . Proof. First it is straightforward that the Min-Max-Delay flow in Fig. 4 given R = n−1 n−2 has a maximum delay no smaller than 1 since R > 1 and thus there always exist some fractional flow rate using upper dashed edges.
Next, we will explicitly construct a feasible flow in the network with unit maximum delay to prove Lem. 7. Note that there are (n − 1) different a 1 − a n paths containing exactly one dashed edge. We then place 1/(n − 2) flow rate on each of these (n − 1) paths with the rate requirement R = (n − 1)/(n − 2) satisfied. The assigned flow rate on each upper dashed edge is 1/(n − 2) which is no larger than the unit capacity and the assigned flow rate on each lower solid edge is (n − 2) × 1/(n − 2) = 1 which is no larger than the unit capacity. Overall the constructed flow is feasible. Since each path only contains one dashed edge, the maximum delay of the constructed flow is 1. Fig. 4 to construct a more complex network with infinite large Int-Gap following Fig. 5. Specifically, we place (n − 2) networks of Fig. 4 (labeled as G * ) side by side disjointly and then connect them to a single source s and a single sink t. All the outgoing edges of s and the incoming edges of t have a capacity of 2 and a delay of 0. The rate requirement now is R = n − 1. Proof. Lem. 8 is proved using the network in Fig. 5.

Now we use
First, we prove that the Min-Max-Delay flow has a maximum delay of 1.
It is straightforward that the Min-Max-Delay flow has a maximum delay no smaller than 1 since the feasible flow with a maximum delay of 0 will have a maximum flow rate of (n − 2) which do not meet the rate requirement R = n − 1.
Now we can route (n − 1)/(n − 2) flow rate to each of the (n − 2) network G * s with the rate requirement satisfied. According to Lem. 7, the minimal maximum delay for (n − 1)/(n − 2) flow rate to pass G * is 1. Thus in this way we have found a feasible flow with the maximum delay of 1 in Fig. 5 and it is the Min-Max-Delay flow.
Next we prove that the Int-Min-Max-Delay flow has a maximum delay of (n − 1)/2 .
Since the rate requirement R = n − 1 is strictly larger than n−2 which is the number of G * s, for any feasible integer flow, there will be at least one G * who is assigned a flow rate of 2. According to Lem. 6, corresponding minimal maximum delay to pass the G * is (n − 1)/2 . Thus, the Int-Min-Max-Delay flow will have a maximum delay of (n − 1)/2 .
Overall, the Int-Gap in Fig. 5 is (n − 1)/2 . Since n can be any positive large integer, the gap is infinite large.

C. Bi-criteria upper bounding the Int-Gap
With the help of a new defined flow f SO d which deletes a certain amount of flow rate from the slowest flow-carrying paths in the integer system-optimal flow which is a special case of the classic min-cost flow [1], this section presents a bi-criteria bound (1 − , 1/ ) for the Int-Gap and gives corresponding tightness analysis.
We note the integality flow theorem holds for min-cost flow as shown in [1]. As a special case, the system-optimal flow defined in this work also has such an integrality property: Theorem 7 (Thm. 9.10 [1]). If all edge capacities, edge delays and rate requirement are integer, the system-optimal flow problem always has an integer system-optimal flow.
Thm. 7 also means if all problem inputs are integers, the total delay of f SO (R) and f SO + (R) are equal.
Now we define f SO d using Algorithm 3. x delete = R //the rate to be deleted 6: while x delete > 0 do 7: Find the slowest flow-carrying path p l 8: if x p l > x delete then 9: x p l = x p l − x delete 10: x delete = 0 11: else 12: x delete = x delete − x p l 13: x p l = 0 First, we obtain a path-based integer system-optimal flow f SO + (R) given rate requirement R (Line 4). Then, the algorithm deletes R rate iteratively from f SO + (R) (Lines 6-15). In each iteration, we find the slowest flow-carrying path p l , i.e., the path that has the maximum path delay among all paths with a positive flow rate, and then delete the right amount of rate from it. Specifically, in the case that p l carries enough flow rate for deletion (Line 8), then its rate is deleted for as much as needed, and the iteration terminates. Otherwise, the rate of p l is all deleted and the iteration continues. The iteration terminates when R rate is deleted in total, and the resulting flow is assigned to Lemma 9. Following Algorithm 3, for f SO d [(1 − )R], we have: Proof. According to Algorithm 3, . We use f k to represent the resulting flow at the beginning of the k-th iteration (or equivalently, at the end of the (k − 1)-th iteration) for 1 ≤ k ≤ K + 1. Obviously, We denote P k as the set of of flow-carrying paths in flow f k , and p k ∈ P k as the slowest flow-carrying path in f k , i.e., the flow with the maximum delay among all flow-carrying paths. According to Algorithm 3, in the k-th iteration in the while loop, we delete some flow rate, say x k > 0, from p k . The flow after deletion is f k+1 .
For the maximum delay, since all edge delays are nonnegative integers, the path delay of all flow-carrying paths cannot increase with reduced flow rate. Thus, the maximum delay cannot increase, i.e., implying that Considering the total delay, for any k, we have In (13), equality (a) holds because e∈p k d e is the path delay of the slowest flow-carrying path p k , i.e., the maximum delay M(f k ) of f k . Equality (b) holds because flow f k+1 is the resulting flow when flow f k deletes x k rate in path p k . Inequality (c) comes from (11) and We then do summation for (13) over k ∈ [1, K], and get which proves (10).
Proof. Considering the definition of f SO + (R) and Thm. 7, we have Leveraging inequality (10) in Lem. 9, it is Here inequality (a) follows (15). For f MM (R), we can route (n − 1)/(n − 2) rate to each of the G * , leading to a maximum delay of 1 which has been proved in Lem. 7. Fig. 6. Integrality theorem does not hold for multi-commodity system-optimal flow problem. All edges have a unit capacity. Solid edges have a delay of zero while dashed edges have a unit delay. There are three source-sink pairs s i − t i , 1 ≤ i ≤ 3, each with a rate requirement of 1.
one path which contains solid edges. Moreover, for any two of the three source-sink pairs, their solid paths share a solid edge. For each source-sink pair, the multi-commodity systemoptimal flow, namely f SO , places half flow rate on the solid path and the remaining half flow rate on the dashed path, leading to a total delay of 1.5. However, the integer multicommodity system-optimal flow, namely f SO + , can only route a unit flow rate using the solid path for one source-sink pair and thus place the unit flow rate requirement on the dashed path for the remaining two source-sink pairs, leading to a total delay of 2 which is strictly larger than 1.5. Therefore, the multi-commodity system-optimal flow must be fractional in some problem instances. Now, if we assume the integrality gap is upper bounded by a ratio of γ for multi-commodity system-optimal flow problem, namely: we can obtain a bi-criteria upper bound of (1 − , γ/ ) for the Int-Gap of our Multi-Min-Max-Delay problem. Now in Algorithm 3 we find the integer multi-commodity system-optimal flow in line 4, the obtained f SO d [(1 − )R] will still has the property of Lem. 9 following the same proof. Considering the assumption (24), proof (15) now becomes: T (f SO + (R)) ≤ γ · T (f SO (R)) ≤ γ · R · M(f MM (R)). (25) Then following the same proof of Lem. 10, it can be proved that M(f SO d [(1 − )R]) ≤ γM(f MM (R))/ . In the end, following the same proof to Thm 8, we can prove the bicriteria upper bound of (1 − , γ/ ) for the Int-Gap of the Multi-Min-Max-Delay problem.

VIII. CONCLUSION
In this paper, we study the Min-Max-Delay single-unicast flow problem which minimizes the maximum end-to-end delay under a rate requirement constraint. We prove it is weakly NPcomplete, and propose a pseudo-polynomial time algorithm to find the optimal solution. We also show that if integer solution is required, the problem becomes strongly NP-complete. An example is given to show that the optimal fraction flow could have smaller maximum delay than the optimal integral flow in Min-Max-Delay.