

![0_image_0.png](0_image_0.png)

a maximal flow EM from s to t in GC , the residual graph RGC (EM ) = (N, ER**) is the**
directed graph obtained from GC **by reversing all arcs belonging to the maximum flow**
EM ; that is, ER = {(x, y) ∈ E \ EM } ∪ {(y, x) | (x, y) ∈ E ∩ EM }**. Given the network**
GC of Fig. 1 and the maximum flow EM of Fig. 2, RGC (EM **) is depicted in Fig. 3.**
Given a maximum flow EM from s to t in GC , given (x, y) ∈ N1 × N2 ∩ E \ EM **, there**
exists a maximum flow containing (x, y) iff (x, y) belongs to a cycle in RGC (EM **) [29].**
Furthermore, finding all the arcs (x, y**) that do not belong to a cycle in a graph can be** performed by building the strongly connected components of the graph. We see in Fig.

3 that the arcs (1, x1) and (2, x1**) belong to a cycle. So, they belong to some maximum** flow and (X1, 1) and (X1, 2) are hybrid consistent. (2, x2**) does not belong to any cycle.** So, (X2, **2) is not HC.**

## 4.1.2 Using The Network Flow For Achieving Hc On **Occurs**

We now have all the tools for achieving HC on any Occurs **constraint. We first build** GC .

We compute a maximum flow EM from s to t in GC ; if val(EM , s, t) < |N1|, we fail. Otherwise we compute RGC (EM **), build the strongly connected components in** RGC (EM ),
and remove from D(Xi) any value v such that (v, xi) belongs to neither EM **nor to a**
strongly connected component in RGC (EM ). Finally, we set ub(T **) to** ub(T )∩Si D(Xi).

Following Theorem 1 and properties of residual graphs, this algorithm enforces HC on Occurs([X1, .., Xn], T ).

Complexity. Building GC is in O(nd) where d **is the maximum domain size. We need** then to find a maximum flow EM in GC **. This can be done in two sub-steps. First, we**
use the arc (v, zv) for each v /∈ lb(T ) (in O(|Si D(Xi)|**)). Afterwards, we compute a**
maximum flow on the subgraph composed of all paths traversing nodes w **with** w ∈ lb(T )
(because there is no arc (w, zw) in GC for such w**). The complexity of finding a maximum flow in a unit capacity network is in** O(
√k · e) if k **is the number of nodes and** e the number of edges. This gives a complexity in O(p|lb(T )| · |lb(T )| · n**) for this second**
sub-step. Building the residual graph and computing the strongly connected components is in O(nd). Extracting the HC domains for the Xi**'s is direct. There remains to compute**
BC on T , which takes O(nd). Therefore, the total complexity is in O(nd+ n · |lb(T )| 3/2).