Magic Loops in Simple Temporal Networks with Uncertainty

A Simple Temporal Network with Uncertainty (STNU) is a structure for
representing and reasoning about temporal constraints and
uncontrollable-but-bounded temporal intervals called contingent links.
An STNU is called dynamically controllable (DC) if there exists a
strategy for executing its time-points that guarantees that all of the
constraints will be satisfied no matter how the durations of the
contingent links turn out.  Recent work has shown an important
connection between the dynamic controllability of STNUs and features
of their associated graphs.  In particular, an STNU is dynamically
controllable if and only if it has no SRN loops---that is,
``semi-reducible'' loops having negative ``reduced path length''.
Morris exploited the structure of such loops to yield an O(N4)-time
DC-checking algorithm, the fastest yet reported in the literature.
(N is the number of time-points in the network.)

This talk continues the exploration of the structure of SRN loops in
STNU graphs with the aim of further improving the performance of
DC-checking algorithms.  First, a notion of indivisibility for SRN
loops is defined.  Next, the number of occurrences of ``lower case''
edges in any indivisible SRN loop is shown to be at most 2^K - 1,
where K is the number of contingent links in the network.  This upper
bound is proved to be tight by providing a recursive procedure for
constructing indivisible SRN loops---called magic loops---that contain
exactly 2^K - 1 occurrences of ``lower case'' edges.  Finally, the
upper bound is exploited to generate an O(N3)-time pre-processing
step for Morris' algorithm that for certain networks reduces the
DC-checking time from O(N4) to O(N3).

Thus, the talk includes both theoretical and practical contributions.
On the theoretical side, it deepens our understanding of the structure
of SRN loops in STNU graphs.  On the practical side, it demonstrates
new ways in which the structure of such loops can be exploited to
speed up existing DC-checking algorithms.