Recent Algorithmic Advances in Simple Temporal Networks with Uncertainty: from Faster Controllability Checking to Faster Execution

This paper presents theoretical and algorithmic contributions that advance the state of the art in the dynamic controllability and dispatchability of Simple Temporal Networks with Uncertainty (STNUs). The first new algorithm, findSRNC, identifies and compactly represents semi-reducible negative (SRN) cycles in STNUs that are not dynamically controllable (DC)—a key step toward repairing such networks. It runs in O(mn + k^2 n + k n log n) time, where n is the number of timepoints, m the number of constraints, and k the number of actions with uncertain durations. This matches the fastest DC-checking algorithms for STNUs and improves on prior SRN-cycle detection methods. It also handles repeated edges—often overlooked in the literature—and uses only polynomial space even when fully expanded SRN cycles would be exponentially large. The second new algorithm addresses dispatchability. Real-time execution of STNUs requires dispatchable ESTNUs (extended STNUs); being DC is not sufficient. In addition, to minimize execution overhead, it is crucial to reduce the number of edges in the dispatchable network. A previous algorithm, minDispESTNU , for computing an equivalent dispatchable network having a minimal number of edges runs in O(k n^3) time. Our new algorithm, minDisp+ESTNU, modifies minDispESTNU to improve its worst-case complexity from O(k n^3) to O(n^3 + k^2 n log n). The third contribution is a rigorous and comprehensive theory of the canonical form of nested diamond structures in dispatchable ESTNUs that greatly facilitates the proofs of correctness for both minDispESTNU and minDisp+ESTNU, while also revealing and enabling the correction of a flaw in a previous algorithm, called fastMinDispESTNU. The fourth contribution is an empirical evaluation of the two new algorithms using an improved open-source implementation to demonstrate their effectiveness. For completeness, the paper first reviews several key existing algorithms from the literature, such as RUL2021 for DC checking, RTE^∗ for real-time execution, and minDispESTNU for dispatchability.