Singly-Connected Multiple Minimal Networks for Efficient Temporal Reasoning About Multiple Clinical Guideline Instantiations

1 Introduction

Clinical Practice Guidelines (CPGs) are "systematically developed statements to assist practitioner and patient decisions about appropriate health care in specific clinical circumstances" (Institute of Medicine, 1990). They support physicians by enabling evidence-based, "standardized", and "optimized" patient treatments. Providing computer-based support for CPGs offers several advantages. For this reason, starting in the 1990s, numerous software systems have been developed to handle Computer-Interpretable Guidelines (hereafter CIGs; see, for example, the surveys in [Peleg and others, 2003; Peleg, 2013; Garc´ıa-Garc´ıa et al., 2024]). Most academic CIG systems are domain-independent and provide physicians with tools for both acquiring CPGs in a formal computer-interpretable representation and executing them to support clinical decision making for individual patients.

CIGs typically include temporal constraints specifying when the different actions should be carried out (e.g., constraints on duration, ordering and delays between actions).

Thus, many CIG formalisms allow the specification of temporal constraints (see, e.g., the survey [Terenziani et al., 2008]). Representing temporal constraints is not enough. Temporal reasoning is also required to verify the consistency of the temporal constraints (if its constraints are inconsistent, it is impossible to apply a CIG to patients without violating some of them), to infer the strictest implied constraints, and to query them. The role of temporal reasoning in the CIG and in the medical contexts is analysed, e.g., in [Terenziani et al., 2008; Combi et al., 2010]. Reasoning on the temporal constraints in a CIG has been addressed by several approaches, including Asbru [Shahar et al., 1998; Duftschmid et al., 2002], GLARE [Terenziani et al., 2001; Anselma et al., 2006], and [Hunsberger et al., 2015]. Recently, several approaches (consider, e.g., [Anselma , 2017; Michalowski et al., 2021; Van Woensel et al., 2023]) have also considered temporal reasoning in the context of comorbidities, in which more than one CIG has to be executed on a patient.

Despite the large amount of existing work, several issues have not been satisfactorily addressed yet. In particular, all the above CIG approaches focus on the management of a single patient. However, in environments such as hospital wards, CIGs may be applied simultaneously to multiple patients. Notably, such executions are mostly independent of each other. Nevertheless, sometimes "crosspatient" temporal constraint must be considered (e.g., the order of access to a shared resource like a laboratory instrument or an operating room). To the best of our knowledge, the only AI approach providing temporal supports for multiplepatient guideline instantiation is [Terenziani Andrea, 2026a; Terenziani Andrea, 2026b; Terenziani Andrea, 2026c]. Such a work grounds on Asbru and on the STP (Simple Temporal Problem) framework [Dechter et al., 1991], and is the starting point of this work. Unfortunately, Terenziani's approach has relevant computational drawbacks, that limit its practical applicability, and that we aim to overcome in this paper.

We propose a new framework based on Bounds on Differences (BoD) (notably, STP is a temporal interpretation of BoD, see Section 2.2) to cope efficiently with the "multiplepatient CIG instantiation" problem (and topologically-similar problems). First, we propose a new constraint model (the singly connected multiple minimal network - SCM-MNet) taking advantage of the topology of the temporal constraints in the "multiple-patient CIG execution" problem. The main idea underlying SCM-MNet is to provide independent minimal networks for independent patients, singly connected by a reference time. In case of addition of "cross-patient" constraints, the minimal networks of the connected patients are merged. We prove that our representation supports an efficient evaluation of the constraints between nodes of the different minimal networks, so that we can obtain the same results that one would obtain by computing the overall minimal network of all the patients (as in [Terenziani Andrea, 2026b]), in a more efficient way. We also show that, even without the overall minimal network, we can still answer queries efficiently.

The paper is organized as follows. Section 2 provides preliminary background and introduces the graph notation for CIG temporal constraints that we adopt in our paper. Section 3 is the core of the paper: it introduces the SCM-MNet and proves its properties, showing how to exploit them for efficient management and query-answering about multiple patients. It also addresses the treatment of "cross-patient" constraints. Section 4 reports an experimental evaluation. Finally, Section 5 presents related work and conclusions, and discusses the generality of our approach.

2 Bounds on Differences and CIGTemporal Constraints

2.1 Bounds on Differences

Bounds on differences (BoD) constraints have received considerable attention in AI. A BoD constraint has the form

where x and y are variables, and c and d are numerical values on a discrete or continuous domain.

BoD constraints can be interpreted in several ways. For example, variables x and y may represent time points, with c and d denoting the minimum and maximum temporal distance between them. This interpretation underlies the STP framework [Dechter et al., 1991], a widely adopted AI approach to temporal reasoning [Vila, 1994; Bart´ak et al., 2022]. Alternatively, c and d may correspond, e.g., to spatial distances between points (see, e.g., [Tas¸ et al., 2014; M¨uller-Hannemann et al., 2004]).

Several AI approaches have been developed to reason over sets of BoD. Given a set of BoD, they define algorithms for constraint propagation aimed at verifying consistency, finding a solution (i.e., an assignment of values to all variables satisfying all constraints), and/or deriving the minimal network (henceforth: MNet) of constraints. The MNet is a constraint set that has exactly the same solutions as the original one, while explicitly representing the tightest possible minimum and maximum implied distances between every pair of variables (see [Dechter et al., 1991] for a formal definition).

Example 1. Let t1, t2, and t3 be time points, and let KB be the following set of BoD constraints: {10 ≤ t2 - t1 ≤ 15, 20 ≤ t3 - t2 ≤ 30, 25 ≤ t3 - t1 ≤ 40}. KB is consistent, and {t1 = 0, t2 = 10, t3 = 30} is one possible solution satisfying KB. The tightest implied constraints (i.e., the MNet) are { 10 ≤ t2 - t1 ≤ 15, 20 ≤ t3 - t2 ≤ 30, 30 ≤ t3 - t1 ≤ 40} In particular, the minimum distance between t1 and t3 is 30.

In many application domains, it is crucial to determine the MNet of constraints, as this provides users with a compact representation of all admissible solutions. This is the case of CIG systems, where the selection of a specific solution within the range of admissible ones must be left to the users. In such contexts, query answering also plays a key role, enabling users to explore the solution space interactively.

The MNet of a set of BoD can be obtained through the application of the famous Floyd-Warshall's all-to-all shortest path algorithm, which operates in cubic time (with respect to the number of variables) [Dechter et al., 1991]. Existing research shows that reasoning and query answering are tightly interconnected tasks. Correct answers to user queries can be guaranteed only if the reasoning process computes the MNet with the tightest constraints (see, e.g., [Van Beek, 1991; Brusoni et al., 1995]). Given the MNet, "take-distance" queries (i.e., queries asking for the minimum distance between a subset of the variables) can be easily answered in linear time with respect to the length of the query (by "reading" the tightest constraints from the MNet). On the other hand, "Yes/No" queries asking about the consistency of a set of BoD constraints with respect to a MNet cannot be evaluated by considering each constraint independently of each other, but require reasoning. In principle, all the BoD in the query should be added to the MNet, and the consistency of the new set of constraints should be evaluated through constraint propagation (e.g., by applying Floyd-Warshall: this is the approach followed, e.g., in [Van Beek, 1991]). However, Brusoni et al proved that, if the MNet is available, then the propagation can be restricted to just the variables explicitly mentioned in the query [Brusoni et al., 1995].

2.2 Modeling Asbru Constraints as BoD: Graph Representation

Asbru adopts temporal annotations (TA) to represent the temporal constraints between actions in CIGs. A TA

• < [minS,maxS], [minE,maxE], [minDu,maxDu], Ref > represents the fact that:
• the action must start betweenminS (first time when act can start) and maxS (the latest time when act can start);
• the action must end between minE and maxE;
• the minimum duration of act is minDu, and its maximum duration is maxDu;
• Ref indicates the CIG reference time (which usually is the starting time of the first action of the CIG);

Asbru temporal formalism provides also additional constraints to fix the order in which actions are to be executed: sequence, parallelism, and "any order". Asbru temporal constraints can be easily mapped onto STP, which is used for temporal reasoning [Duftschmid et al., 2002]. Notably, STP is a temporal interpretation of BoD constraints: a STP constraint ti [c, d] tj stating that tj is between c and d after ti corresponds to the BoD c ≤ tj - ti ≤ d.

A set of BoD constraints can be modeled by a directed graph, in which nodes represent variables and edges are labeled with a weight, representing the minimum distance between them. Thus, the BoD above is represented by two edges (tj -ti ≤ d and ti-tj ≤ -c) while the weight +∞ denotes the absence of a direct edge. Thus Asbru temporal constraints can be translated into BoD constraints [Duftschmid et al., 2002; Terenziani Andrea, 2026a]. In this paper, as in [Dechter et al., 1991], we represent BoD as a directed graph

where V is the set of nodes, E ⊆ V × V is the set of directed edges, and W : V × V → R ∪ {+∞} is a weight function. In general, the input graph G is not complete. We associate to G the complete directed graph

by assigning to every missing edge (i, j) /∈ E the weight ˜ Wij = +∞, and to every existing edge (i, j) ∈ E the weight ˜ Wij =Wij.

Applying Floyd-Warshall's algorithm to a weighted directed graph G = (V, E,W) is equivalent to considering the complete directed graph -→Kn on the same node set V and assigning to each ordered pair of nodes (i, j) the minimum weight of a directed path from i to j in G.

Formally, Floyd-Warshall computes a new weight function W∗ : V × V → R ∪ {+∞} defined by

where the minimum is taken over all directed paths from i to j in G. The resulting graph (called minimal network; MNet for short) -→K ∗n = (V, ˜ E , W∗ ), ˜ E = V ×V,

is thus a complete directed graph whose edge weights represent the tightest bounds induced by path composition in the original graph. Notably, Floyd-Warshall's algorithm can be also used to detect inconsistencies (in case the MNet contains a negative cycle).

2.3 BoD andMultiple Patients Management: Approach in the Literature

In [Terenziani Andrea, 2026a; Terenziani Andrea, 2026b; Terenziani Andrea, 2026c], the authors propose a temporal framework to support multiple-patient instantiations of CIGs (each instantiation corresponding to the execution of a CIG on a patient). They propose a two-level approach, in which the internal level is based on BoD (and, more specifically, on STP), while the external level exploits Asbru's formalism to express temporal constraints, plus a mapping function from/to BoD constraints, and a set of facilities:

• Addition of a new CIG, consisting of (i) the extraction of Asbru temporal constraints from a CIG; (ii) translation into BoD; (iii) temporal reasoning (through FloydWarshall) and creation of a "template" MNet for such a CIG (or detection of inconsistency) (See Figure 1).
• Addition of a new patient for a given CIG, consisting of (i) the instantiation of the CIG "template" MNet for the patient; (ii) temporal reasoning on the set of (temporal constraints about) all the patients (consistency checking and MNet computation, through FloydWarshall)(See Figure 1).
• Addition of a new constraint across actions of different patients: Addition of the new constraint to the over-

all set of patients' constraints (subject to prior consistency verification) and computation of the new MNet.

• Queries. Both "take-distance" and "yes/no" queries (see Section 2.1) are considered;

Notice that the consistency of a CIG is verified when it is added, so that only consistent CIGs (i.e., such that no negative cycle is present in their constraints) are considered in the approach in [Terenziani Andrea, 2026a; Terenziani Andrea, 2026b; Terenziani Andrea, 2026c], as well as in this paper.

Notably, the temporal constraints in a CIG are not "absolute" times, but are relative to the start of the first action in the CIG. Thus, in [Terenziani Andrea, 2026a], the instantiation of the MNet of the CIG to a new patient involves:

• the creation of a copy of the MNet of the CIG, in which new variables are used (replacing the variables in the original MNet)
• the addition of the constraint about the starting time of the execution of the CIG on the patient (expressed as the distance between the starting time and the general reference time RT for all patients - e.g., the birth of Christ).
• the addition of the variables and constraints above to the set of the constraints concerning all the patients
• the application of Floyd-Warshall to compute the new MNet (or to detect an inconsistency)

Notice also that, given the MNet of all the patients, "takedistance" queries just extract the requested constraints, while yes/no queries can be answered efficiently through the application of Floyd-Warshall to the only variables explicitly mentioned in the query (see the discussion in Section 2.1 and [Brusoni et al., 1995]).

3 Efficient Management of Multiple Patients

The approach in [Terenziani Andrea, 2026a; Terenziani Andrea, 2026b; Terenziani Andrea, 2026c] is general, but has a limited scalability. As shown in the experiments in Section 4, when the number of patients increases, the computation of the overall MNet is costly. We overcome such a limitation taking advantage of the nature of the problem and of the topology of the temporal constraints. We optimize two aspects of the approach in 2.3:

1. the instantiation of (the temporal constraints of) a CIG on a patient, and
2. the evaluation of the overall set of constraints (considering all the patients)

We then show that, despite the optimizations we propose (and the fact that we do not evaluate the MNet of the constraints concerning all patients)

1. we retain the query answering efficiency of the approach in 2.3 (which evaluates the overall MNet)

Initially, we consider the above issues without taking into account temporal constraints relating actions of different patients. However, in subsection 3.4, we generalize, showing

1. how to extend our approach (and retain its advantages) in case of cross-patient constraints.

Notice that the rest of this paper is based on the graph notation presented in Section 2.2 above.

3.1 Efficient Patient Instantiation

Introducing a new patient means instantiating (the temporal constraints of) a CIG on the patient. However, as in [Terenziani Andrea, 2026a], we already have the "template" MNet of the CIG's constraints, thus (apart from the introduction of new variables, replacing the ones in the CIG's MNet), then we have only to "anchor" such variables to RT, on the basis of the starting time of the first CIG action for that patient (i.e., on the basis of its distance from RT).

Technically speaking, we have a MNet, plus an additional node (representing RT) which is related to just a node of the MNet (the node representing the starting time of the first action of the CIG, for the patient; indicated by v0 in the following). We prove that the computation of the new MNet (including the new node and edge) can be performed in a time linear in the number of variables (nodes) in the MNet, since

1. Given any pair of nodes in the MNet, their distance is not affected by the addition of RT (termed vnew in Theorem 1) and of the constraints between RT and v0 (see P1.1 below), and
2. ii) The minimal distance between RT and any node vi in the MNet is WRT,0 +W0,i (see P1.2 below)

Theorem 1 (Addition of a uniquely connected node to a MNet). Let Kn = (V, -→E ,W ∗ ) denote the MNet obtained as the weighted transitive closure of an input graph on n nodes by means of the Floyd-Warshall algorithm.

Let vnew /∈ V be a new node added to the graph, and let V ′ = V ∪ {vnew}. We assume that vnew is uniquely connected to the existing graph, i.e., there exists a single node v0 ∈ V such that the only finite-weight arcs incident to vnew are (v0, vnew) and (vnew, v0). All other arcs incident to vnew have infinite weight. Moreover, we assume that Wv0,vnew +Wvnew,v0 ≥ 0, so that no negative cycle is introduced by the addition of vnew (this assumption is obviously true in the CIG context, since we have that Wv0,vnew and Wvnew,v0 represent the exact distance from v0 to RT, so that Wv0,vnew +Wvnew,v0 = 0). Let Kn+1 denote the weighted transitive closure obtained by applying Floyd-Warshall to the augmented graph on V ′ . Then,

• (P1.1) the distances between all pairs of original nodes remain unchanged, i.e.,

• (P1.2) the distances involving vnew can be recomputed through the operator ⊛ (defined within the proof).

Proof. We distinguish two cases.

Case 1: minimal distance between any node i ∈ V and vnew.

Consider an arbitrary node i ∈ V and the shortest-path distance from vnew to i after applying Floyd-Warshall on V ′ . By definition of weighted transitive closure,

Since vnew is uniquely connected, any directed path γ : vnew ⇝ i must necessarily start with the arc (vnew, v0). Hence, every such path can be written as

Therefore,

The inner minimization corresponds exactly to the shortestpath distance from v0 to i in the graph Kn, and thus

If i ̸= v0, any other path from vnew to i would necessarily contain at least one arc of infinite weight and is therefore discarded by the minimization. The case i = v0 trivially yields

Analogously, considering paths from i to vnew, we obtain

Case 2: Distance between any two nodes i, j ∈ V.

Assume by contradiction that there exist i, j ∈ V such that a shortest path from i to j in Kn+1 passes through vnew and yields a strictly smaller weight than W ∗ ij (Kn). Then there exists a path whose weight satisfies

Since vnew is uniquely connected, finite-weight arcs incident to vnew exist only for k = h = v0. The smallest lower bound is obtained by selecting k = i and h = j, which yields

Using the expressions derived in Case 1, we obtain

Since Kn is a weighted transitive closure, it satisfies the triangle inequality, and therefore

Moreover, by assumption, Wv0,vnew +Wvnew,v0 ≥ 0. Combining the above inequalities yields

which is a contradiction. Thus, no shortest path between two original nodes can pass through vnew.

We conclude that applying Floyd-Warshall to the augmented graph preserves all previously computed distances among the original nodes, and only distances involving vnew need to be updated. To do so, we define the operator of uniquely connected node adding ⊛:

by setting

where the entries of W ∗ (K→ n+1 ) are defined as follows:

and

Given Theorem 1, we have the following.

Complexity. Given a MNet -→K (n) containing n nodes, and a new node vnew singly-connected to -→K (n) , the computation of the new MNet -→K (n+1) can be performed in time O(n).

3.2 Singly-ConnectedMultiple Minimal Network

The executions of CIGs on patients are mostly independent of each other. Thus (in the absence of constraints relating actions of different patients), the graph of constraints is partitioned into different subgraphs (one subgraph for each patient), related to each other only by the overall reference time RT. Considering such a topology, we propose to represent the patients' constraints with a new data structure: instead of considering the overall MNet as in [Terenziani Andrea, 2026a], we adopt a set {-→K (k) }mk=1 of MNets (one for each patient) which share a (unique) common node (vRT , representing RT ).

Definition (SCM-MNet). A SCM-MNet is a structure

are k MNets, such that

• they are node-disjoint, except for the node vRT, which is the only common node across all the networks,
• there are no added external connections of finite weights between nodes of different -→K (k) .

Notably, a MNet modeling the application of a CIG to P patients requires space O((N ∗ P)2 ), while the corresponding SCM-MNet requires only O(P ∗ N 2 ) space. More importantly, managing a SCM-MNet has relevant computational advantages (with respect to a unique MNet for all the variables). In the general case, given N variables split in S singly-connected sets of BoD constraints (with N/S variables each), its SCM-MNet can be computed by applying separately Floyd-Warshall to each one of the sets in O(S ∗ (N/S)3 ) (while the computation of the overall MNet would cost O(N 3 )).

Such advantages are amplified in our overall approach, since, following [Terenziani Andrea, 2026a; Terenziani Andrea, 2026b; Terenziani Andrea, 2026c], we pre-compute the template MNet for each CIG (in O(|CIG|3 )) (where |C| denotes the number of nodes in the CIG C), and we operate incrementally, by adding a new patient instance whenever needed. Thus, the addition of a new patient to a SCM-MNet involves a copy (with variable-name replacement) of the template MNet for the corresponding CIG (in O(|CIG|2 ), since the MNet is an all-to-all graph), plus the evaluation of the new MNet for the patient, which, given Theorem 1 above, can be performed in time O(|CIG|). Notably, the complexity of the addition of a new patient is thus independent of the number of patients in our approach, while in [Terenziani Andrea, 2026a; Terenziani Andrea, 2026c] it was cubic in the number of all the variables, since the overall MNet including all the patients was recomputed.

Despite such a major improvement in performance, however, our approach retains the fundamental properties granted by computing the overall MNet. To substantiate this claim, in the following we prove that:

• Given any pair of nodes in one of the MNets -→K (k) , their distance is not affected by the constraints in the other MNets (first case in definition of W target ), and
• Given any pair of nodes belonging to two different MNets, their minimal distance is the sum of their distances from vRT (i.e., the variable representing RT; second case in Definition of W target ).

Theorem 2 (Distances in SCM-MNet.). Given a SCMMNet 〈{-→K (k) }mk=1 , {vRT}〉, let ˜-→K = (V, -→E ,˜ W ) the MNet (weighted transitive closure) of the union of the m MNets (as computed, e.g., by Floyd-Warshall). Then, the resulting weights ˜ W coincide with W target :

Proof. Intra-network case: Let i, j ∈ V (k) for some fixed k ∈ {1, . . . , m}. We show that ˜ Wij =W (k) ij .

Denote by Wγ = ∑(u,v)∈γ Wuv the weight of a directed path γ. Since -→K (k) is a MNet, the value W (k) ij coincides with the minimum weight among all directed paths from i to j entirely contained in V (k) .

Suppose by contradiction that ˜ Wij <W (k) ij .

Then there exists a directed path γ ∗ : i ⇝ j in the graph produced by the unique connection operator such that Wγ ∗ < W (k) ij . In particular, γ ∗ must contain at least one node that does not belong to V (k) .

Claim. The path γ ∗ must contain the node vRT.

If vRT /∈ γ ∗ , then γ ∗ would necessarily contain an arc

or vice versa. By construction of the connection-weight matrix W con , any such arc has infinite weight, i.e., Wuv = +∞. Thus, Wγ ∗ = +∞, which contradicts the assumption that Wγ ∗ <W (k) ij < +∞. Hence, γ ∗ must contain vRT.

Since both endpoints i and j belong to V (k) and vRT ∈ γ ∗ , the path γ ∗ must leave V (k) and re-enter it. So, denoting as v(ρ) a node of another MNet V (ρ) visited by γ ∗ , γ ∗ contains a subpath of the form V (k) -→ V (ρ) -→ V (k) .

By the structure of the unique connection operator, any passage from V (k) to V (ρ) and back must necessarily occur through vRT. We can therefore decompose γ ∗ as

For Wγ ∗ to be strictly smaller than W (k) ij , the subpath vRT ⇝ v(ρ) ⇝ vRT would have to form a negative cycle. However, by hypothesis, no negative cycles are present in any of -→K (i) . This yields a contradiction.

Hence, no such path γ ∗ exists, and we conclude that

Inter-network case: Let

Since vRT is, by construction, common to all minimal networks, it cannot be selected as either the origin or the destination of the path in order to have an inter-network case. As shown above, the only finite-weight paths connecting a node in V (k) to a node in V (ρ) are those that pass through vRT. Indeed, any direct arc between V (k) and V (ρ) has infinite weight and is thus excluded. Let Γij denote the family of all directed paths from i to j with finite total weight. Then every γ ∈ Γij admits the decomposition

Since no cycle γ ρ vRT⇝vRT can be negative, they can be ignored, and we have to solve the minimization problem

Since the two subpaths γi⇝vRT and γvRT⇝j are independent, the minimization decouples, yielding

By definition of MNet, these two quantities correspond to the shortest-path distances W (k) i,vRT and W (ρ) vRT,j , respectively. Therefore,

3.3 Efficient Query Answering

Even without the overall MNet for all the patients (i.e., ˜-→K = (V, -→E ,˜ W ) in Theorem 2) efficient query answering can be performed, thanks to Properties 1 and 2 above.

Take-distance queries. Given a SCM-MNet, distances can be determined in a time linear on the number of pairs (i, j) in the query (see the definition of W target ij in Theorem 2).

Yes/no queries. Let Q be a yes/no query. Let Q′ be its translation into BoD constraints. Let V arQ be the set of BoD variables involved in Q′ . As a corollary of Theorem 2, we have that the MNet considering only the variables V arQ ∪{RT } can be easily computed in O(|V arQ|) and the values we obtain are the same that we would have by computing the overall MNet through Floyd-Warshall (and then considering only the variables in V arQ). Thus, through such a "restricted" MNet, we can answer Q′ in time O(|V arQ|3 ).

3.4 Management of Cross-Patient Constraints

Cross-patient (temporal) constraints relate actions regarding different patients imposing ordering constraints between them. In presence of such constraints, related patients are no more independent of each other, so that temporal reasoning must be performed to determine the MNet (or to detect an inconsistency). However, our approach, based on the partition of constraints into a set of singly-connected MNets, can be extended to cope with this phenomenon. Crosspatient constraints induce a partition of patients into classes of constraint-related patients. For each one of such classes, a MNet is computed (through Floyd-Warshall), leading to a SCM-MNet consisting of a MNet for each class of constraintrelated patients. In such a case

• the complexity of computing SCM-MNet (assuming that N is the number of variables, C is the number of classes and that each class has the same number of variables) is O(C ∗ (N/C)3 ).
• Whenever a new constraint relating two patients Pi and Pj is added, the partition of patients into classes is reevaluated. If Pi and Pj already belong to the same class C ′ , then the constraint is added and the MNet of C ′ is evaluated; otherwise, if Pi belongs to Ci and Pj belongs to Cj, Ci and Cj are merged into a unique class, the constraint is added, and the MNet of the new class is computed.

Notably, cross-patient constraints partition the SCM-MNet structure into MNets, and the complexity is independent of the number of cross-patient constraints in each one of them. In the hospital application context, this results in a "clustering" of constraints mostly based on how patients are partitioned across wards, which makes our SCM-MNet quite effective.

4 Experimental Evaluation

To validate our approach we have also run several experiments. Experiments were conducted on an ASUS VivoBook X512DA laptop with an AMD Ryzen 3 3200U processor (2.60 GHz, 2 cores, 4 threads) and 8 GB of DDR4 RAM, with Microsoft Windows 10 Home (64-bit).

Reproducibility. The reproducibility package for this study is publicly available at https://github.com/terenziani/ Temporal Reasoning for Clinical Guidelines.

Experiment 1, shown in Figure 2, compares the evaluation "from scratch" of a SCM-MNet with respect to the computation of an overall MNet (as in the approach in [Terenziani Andrea, 2026a]; black line), in the simplifying assumptions that all the CIGs have the same number of nodes (20 nodes), and that the cross-related patients distribute evenly into classes of k = 1 (green line), 2 (blue), 4 (purple) and 8 (red) patients each, and considering an increasing number of patients (8, 16, 24, 32, 40) for the MNet approach and the SCM-MNet with k=8 (top part of the Figure) and 200, 400, ... 1000 patients for SCM-MNet.

The experimental evaluation confirms the theoretical analysis: even when patients are cross-related eight-by-eight (SCM-MNet k=8 in Figure 2), the time for 40 patients is 2

minutes and 6 sec. for SCM-MNet, and 49 min. and 23 sec. for the overall MNet. Notably, in 49 ± 1 min., SCM-MNet with k = 8 deals with 1000 patients.

However, patients are usually added one-by-one, so that the addition of a new patient is the crucial process to be optimized. And, indeed, the advantages of our approach with respect to [Terenziani Andrea, 2026a] are so large that it is difficult to plot them in a figure. Indeed, our SCM-MNet approach reduces the complexity from O(N 3 ) to O(|CIG|2 ). For instance, considering again the conditions of Example 1, the addition of 1 patient to the overall MNet of 40 patients takes 53 minutes and 58 seconds while, in our SCM-MNet approach it takes 0.05 seconds. Notably, the complexity of patient addition in our approach is independent of the number of patients.

In the experiment 2, shown in Figure 3, we analyse the time for adding a cross-patient constraint. We consider the most expensive situation for our SCM-MNet approach: the new cross-constraint relates patients belonging to two different classes. In the experiment, we replicate the conditions (e.g., 20 nodes for each CIG) of experiment 1.

Once again, the advantages of our approach emerge clearly. For example, even in the unfavourable case in which k = 8, the time for 40 patients is 2 min. and 6 sec. for SCM-MNet, and 49 min. and 23 sec. for the overall MNet approach.

Finally, we stress that, given Properties 1 and 2, the time for answering queries in our SCM-MNet approach is the same as in the approach computing the overall MNet, and is at most cubic in the dimension of the query, as shown in Figure 4.

5 RelatedWork, Conclusions and Future Work

Since the 80's, temporal reasoning constitutes a wide area of research in AI [Vila, 1994; Stock, 1997; Schwalb and Vila, 1998; Bart´ak et al., 2022], and in AI in medicine in particular [Keravnou and Shahar, 2005; Zhou and Hripcsak, 2007; Combi et al., 2010]. The approach in this paper extends the research in the area of BoD and STP [Dechter et al., 1991; Brusoni et al., 1995; Anselma et al., 2021]. Restricting our attention to CIGs, the survey in [Terenziani et al., 2008] points out several tasks for which temporal reasoning is strictly needed. Thus, several CIG systems have tackled temporal reasoning. A relevant example is the approach in [Hunsberger et al., 2015], which proposes a conceptual model for CIGs that also accounts for temporal constraints and their propagation, while considering uncertainty and alternative execution paths. Further narrowing our scope to STP-based approaches, besides Asbru (see Section 2.2), we also mention GLARE [Terenziani et al., 2001; Terenziani et al., 2002; Anselma et al., 2006], which introduces a high-level temporal language based on an extension of STP to handle periodic constraints. GLARE includes temporal reasoning algorithms for propagating such constraints and provides proofs of their correctness and completeness.

Notably, the CIG temporal reasoning approaches mentioned so far focus on temporal reasoning related to a single CIG and/or the application of a CIG to a specific patient. Recently, several CIG approaches have focused their attention on the simultaneous applications of multiple CIGs to manage a multi-disease (comorbid) patient [Van Woensel et al., 2023]. In such a context, temporal reasoning plays a crucial role to temporally detect possible CIG interactions dangerous for the patient, and to merge different CIGs executions (consider, e.g., [Anselma et al., 2017; Michalowski et al., 2021; Van Woensel et al., 2023]). However, also such approaches focus on the management of a single patient.

To the best of our knowledge, the only CIG temporal reasoning approach that considers multiple patients is the one in [Terenziani Andrea, 2026a; Terenziani Andrea, 2026b; Terenziani Andrea, 2026c], discussed in Section 2.3, which has relevant limitations in terms of computational efficiency.

We propose a new framework which overcomes such limitations. The core innovative contributions of our work are:

• The identification of a new representation (SCM-MNet) for temporal constraints and the proof of its properties;
• An efficient procedure, exploiting such properties to add a new CIG instantiation for a new patient, still maintaining the capability of answering queries efficiently;
• An experimental evaluation that further confirms the advantages of our approach, which makes BoD-based temporal reasoning scalable for contexts such as medical scheduling;
• Last, but not least, our approach is general (see below).

A final important remark concerns the generality of our approach. First of all, though our current work adopts Asbru, any other formalism mappable onto BoD can be used. Much more importantly, though our approach is motivated by our work in the CIG context, the methodology we propose and the properties we prove apply to BoD in general, so that they can be applied in any context in which a "partitioning" of BoD constraints into singly-connected partitions is possible. In particular, in the short term, we envision an application of our approach to the context of workflows [Bettini et al., 2002; Combi et al., 2012; Combi et al., 2019].

As future work, we also envision the possibility to improve the flexibility of our approach along two parallel directions. First, we plan to extend BoD with preferences and/or probabilities, following the lines addressed in [Anselma et al., 2021; Andolina et al., 2022]. Second, we want to explore the possibility of distinguishing between contingent and requirement constraints and considering the related dynamic controllability problems, along the lines addressed in [Lanz et al., 2013; Posenato and Combi, 2023].