Computational Complexity of Repair Problems on Simple Temporal Networks with Uncertainty

Simple Temporal Networks with Uncertainty (STNUs) are a well-established formalism for reasoning about temporal plans involving uncontrollable durations, known as contingent links. This model enables checking the controllability of plans under different assumptions about when uncertainties are revealed (Weak, Dynamic, and Strong Controllability). Recent work has also introduced methods to repair uncontrollable STNUs by adjusting contingent bounds, which is relevant e.g., in multi-agent systems, or resource-aware settings where some external flexibility can be negotiated. Nevertheless, there remains a lack of formal understanding regarding the computational complexity of such repair problems. This paper fills that gap by formally defining the problems and assessing the complexity of a number of them. In particular, we show that for a number of settings, repair is no harder than controllability.