Faster Dynamic Controllability Checking in Temporal Networks with Integer Bounds

1 Introduction

In temporal planning, an agent is presented with a series of events and must decide precisely when to schedule them. These events are often subject to constraints and the role of the agent is to construct a schedule that respects those constraints. This scheduling problem becomes more difficult when certain events are outside of their control. In such a situation, the agent is concerned with knowing whether a schedule can be constructed in real-time during execution, or whether the temporal problem is dynamically controllable.

In this paper, we introduce an improved algorithm for checking the dynamic controllability of Simple Temporal Networks with Uncertainty (STNUs) with integer bounds for its constraints. Our algorithm is based largely on two existing dynamic controllability algorithms: one that runs in O(n3 ) time [Morris, 2014] and a faster one that runs in O(mn + k2n + n logn) [Cairo et al., 2018], where n represents the number of events in a temporal network, m represents the number of temporal constraints, and k represents the number of uncontrollable events in the temporal network. Our algorithm applies some of the ideas from the faster algorithm, namely the use of a potential function to re-weight edges, to significantly speed up the O(n3 ) algorithm, dropping the overall runtime to O (min(mn,m√n logN) +km+k2n+kn logn), where N is the magnitude of the most negative edge weight in the STNU's graphical representation.

The requirement that all constraint bounds be integer is not overly restrictive in practice, as STNU bounds are often derived from human-specified characterizations and requirements on temporal events. When the integer constraint is relaxed, our algorithm still matches the best-known runtime of O(mn + k2n + n log n). However, because we base our algorithm off of the O(n3 ) algorithm, which importantly uses length-preserving rules, we believe it is straightforward to transfer these same runtime improvements to other algorithms that rely on dynamic controllability checking variants, such as checking dynamic controllability for chain-free Partially Observable Simple Temporal Networks with Uncertainty [Bit-Monnot et al., 2016] and checking the delay controllability of STNUs [Bhargava et al., 2018], but this work is outside the scope of this current paper.

2 Background

Simple Temporal Networks (STNs) provide a way to formally model events, or timepoints, and the temporal constraints between them (e.g. event A must happen at least 20 minutes after event B) [Dechter et al., 1991]. STNs, however, are incapable of modeling events that cannot be scheduled explicitly. These types of events are quite commonplace and effective agents must be capable of handling them in their plans (e.g. it is impossible to schedule that the time spent driving across town is exactly 22 minutes because it is highly dependent on traffic). Simple Temporal Networks with Uncertainty (STNUs) provide an explicit way to model this type of uncertainty [Vidal and Fargier, 1999].

Definition 1. STNU [Vidal and Fargier, 1999]

An STNU is a 4-tuple 〈Xe, Xc, Rr, Rc〉 where:

• Xe is the set of executable timepoints
• Xc is the set of contingent timepoints
• Rr is the set of requirement constraints of the form lr ≤ xr - yr ≤ ur, where xr, yr ∈ Xb ∪ Xe

• Rc is the set of contingent constraints of the form 0 ≤ lr ≤ cr - er ≤ ur, where cr ∈ Xc, er ∈ Xe

STNUs subdivide their timepoints into a set of executable timepoints and contingent timepoints. Executable timepoints are those that are explicitly scheduled by the agent, and contingent timepoints represent stochastic events that are scheduled by nature. The constraints of an STNU are subdivided into requirement constraints and contingent constraints. Requirement constraints are ordinary constraints like those found in an STN. Contingent constraints impose a relation between a starting executable timepoint and an ending contingent timepoint describing when the contingent timepoint is guaranteed to happen in relation to the starting timepoint. When considering the runtime of algorithms over STNUs, we let m represent the total number of constraints, n the total number of timepoints, and k the total number of contingent timepoints.

Because many of the timepoints are outside of the control of the scheduler, it is often overly restrictive to construct a static schedule to determine the feasibility of an STNU. Instead, we often consider its dynamic controllability [Vidal and Fargier, 1999]. We say that an STNU is dynamically controllable if it is possible for an agent to construct a schedule during execution if they learn about the true value of contingent timepoints as they happen.

When trying to determine STNU dynamic controllability, we often prefer to work with their labeled distance graph representation [Morris, 2006]. In the labeled distance graph, each timepoint of the STNU corresponds to a node in the graph. Each requirement constraint of the form u ≤ B-A ≤ v is split into two edges, A v-→ B and B -u --→ A. Contingent constraints of the form u ≤ C - A ≤ v (where C is a contingent timepoint) produce four edges. As was the case for requirement constraints, we produce edges A v-→ C and C -u --→ A, but we also produce two labeled edges: the uppercase edge C C:-v ---→ A and the lower-case edge A c:u --→C. It is clear by construction that there are O(m) edges in the graph, O(n) nodes in the graph, and O(k) labeled edges.

These edges directly map to constraints that apply to the STNU that produced them. Unlabeled edges represent unconditional constraints that always apply whereas labeled edges represent conditional constraints that only apply if the label's corresponding contingent constraint takes on its longest or shortest possible value, for upper-case and lower-case labels respectively.

Just as constraints can be combined to create new constraints, so too can these edges be combined to produce new edges. [Morris, 2006] introduced a sound and complete set of edge reduction rules for use in an STNU's labeled distance graph:

• Upper case reduction: With edges A x-→ B C:y --→ D, produce edge A C:(x+y) -----→ D.
• Lower case reduction: With edges A b:x --→ B y-→ C, if y < 0, produce edge A x+y ---→ C.
• Cross case reduction: With edges A b:x --→ B C:y --→ D, if

• No-case reduction: With edges A x-→ B y-→ C, produce A x+y ---→ C.
• Label removal: With edge A B:x --→ C, if x ≥ 0, produce A x-→C.

To determine whether an STNU is dynamically controllable, it suffices to determine whether the STNU's labeled distance graph has a semi-reducible negative cycle [Morris, 2006]. A semi-reducible negative cycle is a cycle whose total weight is negative and when after applying a series of reductions, we are left with a cycle without lower-case edges. The current best-known runtime for finding a semi-reducible negative cycle with this particular set of edge reductions is O(n3 ) [Morris, 2014].

In this paper we will use an augmented version of this ruleset and introduce the unconditional reductions, which comes in two flavors: unconditional-upper and unconditional-lower. While these rules are used to prove correctness, we do not use these rules directly in the execution of our algorithm. The following lemmas demonstrate that the two rules are sound.

Lemma 2.1. Unconditional-Upper Reduction

If we start with edges A C:u --→D and D v-→B, then we can add edge A C:u+v ----→ B.

Lemma 2.2. Unconditional-Lower Reduction

If we start with edges A c:u --→D and D v-→B, then we can add edge A c:u+v ----→ B.

Proof. We can use the same proof strategy for both lemmas. Let α be the label for the first edge in the sequence. The first edge provides the conditional constraint that xD - xA ≤ u that depends on the condition α (it holds either if C takes on its maximal or minimal value depending on if α is an upper or lower case label, respectively). The second edge provides the unconditional constraint that xB - xD ≤ v. When we combine the two, we get that xB - xA ≤ u + v when the condition associated with α holds. This yields the output edge as specified in both lemmas.

While the current state-of-the-art algorithm uses a different set of rules for checking dynamic controllability [Cairo et al., 2018], we show in this work that if we restrict our focus to constraints with integer bounds, we can continue to use the existing ruleset from [Morris, 2006] and improve on the best-known runtime for checking dynamic controllability under any ruleset.

3 Algorithm

Our contribution in this work is in demonstrating how a small set of modifications to the existing O(n3 ) algorithm for determining dynamic controllability [Morris, 2014] can lower the asymptotic worst-case runtime. This improvement is primarily realized by modifying the underlying labeled distance graph of our input STNU by finding a graph re-weighting through the application of a potential function as used by [Cairo et al., 2018].

Input: A labeled distance graph G = 〈V, E〉 and non-negative potential function ψ

Output: Whether the STNU derived from the distance graph is free of semi-reducible negative cycles.

Initialization:

• 1 negNodes ← the set of all vertices with incoming negative edges under the potential function ψ;

SRNCFREE?:

• 2 for v ∈ negNodes do 3 cycleFree? ←SRNCDIJKSTRA(G, v, ψ, [v], negNodes); 4 if !cycleFree? then
• 5 return false;
• 6 return true;

Algorithm 1: Semi-Reducible Negative Cycle Algorithm

We begin by introducing the core algorithms responsible for checking for the presence of a semi-reducible negative cycle and, by proxy, whether the STNU is dynamically controllable. Algorithms 1 and 2 are virtually identical to the ones presented in [Morris, 2014], and we rely quite heavily on the analysis in that work proving their correctness.

Briefly, the algorithm for checking dynamic controllability traverses the graph in reverse applying edge reductions as it goes in order to maintain a semi-reducible path. In its traversal, it uses a variant of Dijkstra's algorithm to ensure that it considers the shortest paths from its start node and has additional checks (e.g. line 18 of Algorithm 2) to guarantee that the path is semi-reducible. Dijkstra's algorithm, however, does not work in general with negative edges but will work properly if the only negative edge is the first one. The goal of the algorithm is to show that every walk from a negative edge eventually becomes positive; if so, there can be no semi-reducible negative cycles in the graph. If the dynamic controllability check runs into a negative edge that is not the first in its path during its walk, it recursively calls Dijkstra's algorithm again (line 14). If a sub-call returns, it adds all of its walks (which have positive length) to the graph so that callers can use them in their walks (line 10). If an infinite recursion is detected (line 5), then we know that each recursive call was made while it was in the midst of a semi-reducible negative walk, and the union of all of those walks yields a semi-reducible negative cycle. The negNodes list in Algorithm 1 guarantees that all negative edges are considered.

This original variant of this algorithm runs in O(n3 ) time, and this can be seen by analyzing the runtime of SRNCFREE? (Algorithm 1) and the main algorithm it calls into, SRNCDIJKSTRA (Algorithm 2). For each call to SRNCDIJKSTRA and its terminal node, s, the algorithm runs a version of Dijkstra's algorithm over a subset of the graph that is composed of non-negative labeled and unlabeled edges, as well as positive edges that are derived through edge production rules. If no new edges were produced, each subcall would take O(m + n logn) time but instead we must argue that it takes O(m′ + n logn) time where m′ is the total number of edges in the graph after all edges are added into the graph. We know that each call to SRNCDIJKSTRA can add at most O(n) new edges to the graph (by adding an edge from each node of the graph to s), so to bound the total number of new edges, we have to bound the number of calls to SRNCDIJKSTRA. In the worst case, there are n total calls to SRNCDIJKSTRA, meaning that the total runtime is O (n(m + n2 + n log n)) = O(n3 ) time.

The goal of our new set of algorithms is to minimize the number of calls to SRNCDIJKSTRA thus decreasing the overall runtime. The way we intend to do so is by introducing a potential function to re-weight the edge to decrease the total number of nodes with incoming negative edges.

3.1 Correctness under a Potential Function

We argue that by being smart about our choice of potential function, we can adapt an existing dynamic controllability checking algorithm and significantly improve its performance. We present such an adaptation below (Algorithms 1 & 2). The primary difference between the original controllability checking algorithm and the one presented here is that our modified function takes in a potential function ψ over the nodes that re-weights the edges of the graph such that the new weight ˜w of an edge going from u to v is given by ˜w = ψ(v) + w - ψ(u). The algorithm is evaluated with respect to the edge weights under the potential function and has a slight change (see line 18 of Algorithm 2) when checking whether lower- and cross-case edge reductions apply. With this change, our algorithm searches for a cycle that is negative under the potential function but semi-reducible when considering the original set of weights. Because a cycle's total weight is not affected by a potential function, the result is an algorithm that is able to find a semi-reducible negative cycle in our original graph.

To prove that our approach is correct, we must first show that introducing and applying a potential function to our labeled distance graph does not affect the correctness of the algorithm. We do this by first showing that when an STNU is uncontrollable, our algorithm correctly returns false, independent of the specific potential function, and second by showing that for certain potential functions, when we pass in an STNU that is controllable, our algorithm correctly return true.

Theorem 3.1. Given an STNU S that is not dynamically controllable and a potential function ψ over the nodes of S's labeled distance graph, Algorithm 1 will return false on inputs S and ψ.

Proof. If S is not dynamically controllable, then there exists a semi-reducible negative cycle C in S's labeled distance graph. Let r be the number of edges in C and let ei represent the ith edge in C.

We now construct a new labeled distance graph G′ derived from S's labeled distance graph, where each vertex v is replaced with three nodes, vin, v′ , and vout. Each edge of the original labeled distance graph of the form A w -→ B is transformed into Aout w -→ Bin. For each vertex v, we also add edges vin ψ(v) ---→ v′ and v′ -ψ(v) ----→ vout. Each edge ei = A w -→ B of our cycle C is now implicitly represented by three edges, ei,in = A′ -ψ(A) ----→ Aout, e′i = Aout w -→ Bin, Input: Labeled distance graph G = 〈V, E〉, terminal node s, non-negative potential function ψ, callStack, and negative nodes negNodes

Output: Whether the current walk is cycle-free Initialization: 1 Q←PriorityQueue(); 2 for e ∈ s.incomingEdges() do 3 if e.weight(ψ) < 0 and !e.lowerCase() then 4 Q.add(〈e.f rom, e.label〉, e.weight(ψ)); SRNCDIJKSTRA: 5 if s ∈ callStack[1 : end] then 6 return false; 7 while Q.size() > 0 do 8 v, label, weight ← Q.pop(); 9 if weight ≥ 0 then 10 G.add(〈v, s, weight〉); 11 else 12 if v ∈ negNodes then 13 newStack ← [v].concat(callStack); 14 result ← SRNCDIJKSTRA(G, v, ψ, newStack, negNodes); 15 if !result then 16 return false; 17 for e ∈ v.incomingEdges() do 18 if e.weight(ψ) ≥ 0 and !(e.isLowerCase() and (e.label == label or weight - ψ(s) + ψ(v) ≥ 0)) then 19 w ← e.weight(ψ) + weight; 20 Q.addOrDecKey(〈e.from, label〉, w) 21 negNodes.remove(s); 22 return true;

and ei,out = Bin ψ(B) ---→ B′ . If we expand all edges ei in place, we get a new cycle C ′ that is of length 3r.

It is important to realize that C ′ is also a semi-reducible negative cycle. Each ei,out and ei+1,in pair can be joined in a no-case reduction to produce some edge vin 0-→ vout. This zero-length edge can then be immediately folded into e′i by either an application of an unconditional, upper-case, or nocase reduction, meaning after a series of several reductions all that remains are the original edges from C that instead connect all the vout vertices.

In order to show that Algorithm 1 returns the correct answer when given an STNU that is not dynamically controllable, we show that when given S and ψ, it is simulating a search for a semi-reducible negative cycle in G′ , using the original O(n3 ) algorithm. Because G′ has a semi-reducible negative cycle whenever S does, this is sufficient to prove our claim.

It is clear by the construction of Algorithm 2 that it simulates checking G′ . The inclusion of an edge A -→ B from S's labeled distance graph in a path necessitates the inclusion of A′ -ψ(A) ----→ Aout, Aout -→ Bin, and Bin ψ(B) ---→ B′ from G′ . Algorithm 2 thus acts as if it is implicitly optimizing for this construction and simulates the selection of these three edges simultaneously (since no other subpaths involving that edge are possible) through the selection of the edge under the potential function. The modified check at line 18 guarantees that the path is still semi-reducible by removing the application of the potential function, so we have a guarantee that all paths considered by the algorithm are semi-reducible and the structure of Algorithm 1 guarantees that we will consider all negative edges in our walk. Thus, Algorithm 2 behaves as if it is checking for a semi-reducible negative cycle in G′ , so if S is not dynamically controllable, the algorithm will correctly return false on S and ψ.

It is not clear whether the reverse condition holds in general, or whether applying any potential function to an STNU's labeled distance graph guarantees that a controllable network remains controllable. However, we can prove that this result holds for a specific subset of cases, namely for potential functions that are non-negative for all vertices. If we demonstrate this, then it is clear that if we find such a potential function and apply it to an STNU, we have a guarantee that our Algorithm returns true if and only if the original STNU is dynamically controllable. Note that for any potential function, it is trivial to create one that satisfies this condition; we simply add a large constant uniformly to all potential values, which leaves the induced edge weights entirely unaltered.

Theorem 3.2. Given a dynamically controllable STNU S and a potential function ψ over S's labeled distance graph such that for each vertex v, ψ(v) ≥ 0, Algorithm 1 returns true.

Proof. To show that our algorithm will recognize S as dynamically controllable, we construct a new STNU S′ that we use to analyze the algorithm's behavior. S′ is identical to S except that every vertex v is split into v and v′ . For every vertex v, a single requirement link is created ψ(v) ≤ v′ - v ≤ ψ(v). Because ψ ≥ 0, it is clear that S′ is also dynamically controllable because any valid strategy for S would similarly work for S′ if it were augmented by a guarantee that for all v, v′ was executed ψ(v) units of time after v.

If we inspect the behavior of our algorithm on S and ψ, we observe that it simulates the behavior of the original O(n3 ) algorithm on S′ with one minor deviation. As the algorithm walks the graph, every time it reaches some vertex v, it immediately takes the (reverse) v′ -ψ(v) ----→ v edge. When that path is popped from the queue at a later point, its only option is to take the v ψ(v) ---→ v′ edge in essence reversing its previous decision. Rather than exploring each detour one at a time, it groups them in three, as was described in the previous theorem. The modified check at line 18 again guarantees that lower-case edges are properly checked for elimination as their values are temporarily shifted because of the potential function. Thus, we know that if our algorithm were to return false, we would arrive at a contradiction because it would mean that S′ is not dynamically controllable.

With these two theorems, we have now shown that Algorithm 1 checks the dynamic controllability of an STNU correctly when also given a potential function. However, we have neither shown how to derive this potential function Input: A labeled distance graph G = 〈V, E〉 and potential function ψ Output: Whether the STNU given by the labeled distance graph is dynamically controllable. Initialization: 1 loProj ←a projection of graph G that only contains lower-case and unlabeled edges with all labels removed; 2 N ← the minimum value such that all edge weights satisfy w ≥ -N as well as N ≥ 2; CHECKDC: 3 if (√|V | < logN) or G has non-integer constraints then 4 φ← BELLMANFORDPOTENTIALS(loProj); 5 else 6 φ← GOLDBERGPOTENTIALS(loProj); 7 if φ == ∅ then 8 return false; 9 ψ ←-φ; 10 ψ.addToAll(-ψ.min); 11 return SRNCFREE?(G, ψ); Algorithm 3: Full Dynamic Controllability Checking Algorithm Input: A graph stripped of all labels G = 〈V, E〉 Output: A potential function φ or ∅ if G has a negative cycle Initialization: 1 for v ∈ V do 2 φ(v) ← 0; BELLMANFORDPOTENTIALS: 3 for i ∈ [1..(|V | - 1)] do 4 for e ∈ E do 5 φ(e.start) ← max(φ(e.start), φ(e.end) - e.weight); 6 for e ∈ E do 7 if φ(e.start) + e.weight - φ(e.end) < 0 then 8 return ∅; 9 return φ;

Algorithm 4: Algorithm for finding potential function, from [Cairo et al., 2018]

nor why including a potential function would improve overall running time. In the rest of this section, we will explain these two points, ultimately demonstrating our desired runtime.

3.2 Generating Potential Functions &Runtime Complexity

In Algorithm 3, we introduce the full algorithm that we will use to evaluate the dynamic controllability of an STNU. Our algorithm starts by finding a potential function, making its values entirely non-negative, and then checking dynamic controllability with respect to that potential function. We will start by briefly describing the algorithms for deriving a potential function.

There are two functions that we use to derive our potential functions, BELLMANFORDPOTENTIALS (line 4, Algorithm 3) and GOLDBERGPOTENTIALS (line 6, Algorithm 3). BELLMANFORDPOTENTIALS is elaborated in full in Algo- Input: A graph stripped of all labels G = 〈V, E〉 and edge weights given by l Output: A potential function φ or ∅ if G has a negative cycle Initialization:

1 for v ∈ V do 2 φ(v) ← 0; 3 lp ← l;

• 4 G- ←G restricted to negative and zero-length edges;

GOLDBERGPOTENTIALS:

5 if min(l) < -1 then 6 l′ ← ⌈ l2 ⌉; 7 φ← GOLDBERGPOTENTIALS(G, l′ ); 8 if φ == ∅ then 9 return ∅; 10 for u, v ∈ V 2 do 11 lp(u, v) ← l(u, v) + 2φ(u) - 2φ(v); 12 components ←G-.stronglyConnectedComps(); 13 for c ∈ components do 14 if c.hasNegativeEdge() then 15 return ∅; 16 G-.contract(c); 17 G-.addNode(s); 18 for v ∈ G-.nodes() do 19 G-.addEdgeWithWeight(s, v, 0); 20 for i ∈ [1...|V |] do 21 Li ← {v ∈ G-.nodes()|dist(s, v) = -i}; 22 r ←maxr(r|Lr ̸= ∅); 23 q ← argmaxq(|Lq|); 24 if r ≥ √k then 25 φ.adjustChain(Lr); 26 else 27 φ.adjustLayer(Lq); 28 return φ;

Algorithm 5: Algorithm for finding potential function, from [Goldberg, 1995]. For more details and analysis, please see the original paper.

rithm 4 and maps exactly to a combination of INITPOTENTIAL and NEGATIVECYCLE from Algorithm 3 of [Cairo et al., 2018]. It runs a variant of the Bellman-Ford algorithm computing a potential function along the way. If after a certain number of iterations, it has not found a potential function φ such that for all edges u w -→ v, φ(u) + w - φ(v) ≥ 0, then it knows that the input must have a negative cycle.

GOLDBERGPOTENTIALS (Algorithm 5) is reproduced from the pseudocode in [Goldberg, 1995]. The algorithm attempts to construct a potential function φ that for each edge u w -→ v, φ(u) +w -φ(v) ≥ 0; if it is unable to do so, it determines that there must be a negative cycle in the graph. The algorithm builds its potential function using a scaling mechanism and at each level either finding a long chain of potential values it can adjust at once or a large layer of potential values to adjust at once. Because it successively scales its arguments, it requires that all edge weights be integer. Overall, the algorithm runs in O(m√n logN) time.

By default, these algorithms do not produce the potential function we want. Our proofs depended on having a potential function that satisfied ψ(v) + w - ψ(u) ≥ 0. If we let ψ = -φ (line 9), then the two sub-calls would yield -ψ(u) + w + ψ(v) ≥ 0, as we wanted. This potential function, however, may not be positive, but if our algorithm is considering a potential function, line 10 of Algorithm 3 will ensure that the potential function has no non-negative values. Theorems 3.1 & 3.2 will also guarantee that we return the correct answer when we call SRNCFREE?, so what remains is to consider what happens when we fail to find a potential function.

Both algorithms will fail to yield a potential function if and only if the input loProj has a negative cycle, and when we cannot find a potential function, Algorithm 3 returns false. If we assumed that this response were incorrect, i.e. that the input loProj had a negative cycle but the STNU were dynamically controllable, we would quickly run into a contradiction. If loProj had a negative cycle, then that means that there exists some combination of unlabeled and lower-case edges that form a cycle with negative weight. However, if we considered the case where all of our contingent constraints took on their minimum possible value, we would enforce the constraints of all lower-case edges since their conditions apply. In such an instance, we would be unable to execute our STNU. To see this, consider the constraints that we would derive by combining the constraints associated with adjacent edges. Each pair of adjacent edges are represented by constraints of the form C - B ≤ u and B - A ≤ v and yield constraints of the form C - A ≤ u + v. Because the edges form a cycle, we would eventually reach a point where we would have two constraints C-A ≤ w and A-C ≤ w′ that would combine to form 0 ≤ w + w′ . But because the edge production rules are length-preserving, we know that w + w′ represents the total weight of the cycle which is negative, meaning we have a contradiction. Thus, our algorithm will correctly determine an STNU's dynamic controllability, and we can now provide a thorough analysis of our algorithm's runtime.

Theorem 3.3. Algorithm 3 runs in worst-case O (min(mn,m√n logN) +km+k2n+kn logn) time for STNUs with integer bounds.

Proof. First, we look at the runtimes of the lines used to derive the potential functions (lines 4, 6). BELLMANFORDPOTENTIALS runs a variant of the Bellman-Ford algorithm to search for a negative cycle and constructs a potential function if one does not exist. It iterates through each edge for as many times as there are nodes in the graph, causing it to run in O(mn) time. In contrast, GOLDBERGPOTENTIALS uses a scaling algorithm to either find a potential function or determine that the graph has a negative cycle; this algorithm takes O(m√n log N) time and requires that all edge weights be integers [Goldberg, 1995]. We know that if √n < logN, then, in the limit, BELLMANFORDPOTENTIALS runs faster than GOLDBERGPOTENTIALS. Because we selectively choose which function to run based on exactly that inequality (line 3), we know that the set of operations through line 8 takes O(min(mn,m√n logN)) time. If the search for a potential function instead yields a negative cycle, then we terminate immediately, satisfying the worst-case runtime.

We now consider what happens if we our initial checks yield a valid potential function. The update at line 9 ensures that the minimum value of ψ is 0 and involves at most O(n) time to search for the minimum value and then update each value of ψ. This does not change the re-weighted values of any edges under ψ as the start and endpoints of each edge change by the same amount.

What remains is to analyze the runtime of SRNCFREE? (Algorithm 1). We begin by looking at SRNCDIJKSTRA (Algorithm 2). By the original analysis, if we let c be the number of times that SRNCDIJKSTRA is called, the overall runtime of the algorithm is given by O(c(m+ cn+n logn)). The worst case is that all nodes have incoming negative edges and so SRNCDIJKSTRA is called once for every node. However, in our work we invoke the algorithm once for every node with an incoming negative edge under the potential function ψ. Our construction of ψ guarantees that when it is applied to all lower-case and unlabeled edges, the new edges are all nonnegative. Thus, the only edges that can be negative under ψ are upper-case edges. Because there is exactly one upper-case edge per contingent link of STNU, SRNCDIJKSTRA is called at most O(k) times and at most O(kn) edges are added to the graph in total.

Thus, SRNCFREE? takes O(k(m+kn+n logn)) time, which means that our total runtime is O (min(mn, m√n log N ) + km + k2n + kn log n).

If we do not have a guarantee that our temporal constraint bounds are all integer, much of the same analysis can be applied, but we instead always use BELLMANFORDPOTENTIALS. This brings the total runtime to O(mn + k2n + kn logn), which matches the best runtime for general dynamic controllability checking [Cairo et al., 2018]. Unlike the other algorithm, however, our approach does not require any updates to the potential function as our algorithm is able to use the existing ruleset from [Morris, 2006] which guarantees that all transformations are length-preserving. This approach means that other algorithms that are heavily based off of the [Morris, 2014] algorithm, such as checking the dynamic controllability of chain-free POSTNUs [Bit-Monnot et al., 2016] and checking the delay controllability of STNUs [Bhargava et al., 2018], can likely similarly improve their runtimes to the stated bounds with minimal changes to their core algorithms.

4 Conclusion

In this paper, we introduce a modification to an existing O(n3 ) algorithm for determining dynamic controllability and show how this slight change speeds up the theoretical worst-case of our algorithm. Our final algorithm runs in O (min(mn,m√n logN) +km+k2n+n logn) for temporal networks with integer bounds, which is the best-known runtime for checking dynamic controllability. Even when relaxing the integer bound requirement, our algorithmmatches the best available runtime for checking controllability but the simplicity of the change means that this algorithm strategy is likely to apply to many other variants of STNU dynamic controllability checking.