Consider Algorithm 1 that finds the lexicographically smallest solution of the REGULAR constraint. At line 7 it invokes a DC propagator for the REGULAR constraint to ensure that an extension of a partial solution on each step leads to a solution of the constraint. To do so, it prunes all values that are inconsistent with the current partial assignment. We will show that for the REGULAR constraint values consistent with the current partial assignment can be found in O(log(d)) time.

Let Gx be a layered graph for the REGULAR constraint and Li = [L[1]**, . . . , L**[i]]
be a partial assignment at the ith iteration of the loop (lines 4 - 6, Algorithm 6). Then Li corresponds to a path from the initial node at 0th layer to a node q i j at ith layer. Clearly, values of X[i **+ 1]** consistent with the partial assignment Li are labels of outgoing arcs from the node q i j
. We can find the label with the minimal value in O(log(d)) time.

Algorithm 6 shows pseudo-code for REGULARmin(A, L, X). Figure 2 shows a run of REGULARmin(A, L, X) for variables X in Example 4. The lexicographically smallest solution corresponds to dashed arcs.

Algorithm 6 REGULARmin(A, L, X)
1: **procedure** REGULARmin(A : in, L : **out,** X : in)

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

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

The time complexity of Algorithm 2 for the REGULAR constraint is also O(nT ).

The algorithm works with the layered graph rather than original variables. On each step it marks edges that occur in feasible paths in Gx that are lexicographically greater than or equal to L. Figure 3 shows execution of C&LEXlb(Xl, Y , REGULAR) for vari-