

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

Proposition 1. The ULC relation p *can be entailed by basic CDC constraints.*
Proof. Two auxiliary variables w1 and w2 are introduced. Let

$$\begin{array}{c}{{{\mathcal{N}}_{\!\!\tau}=\left\{u\;O\;w_{1},w_{1}\;E\!:\!S E\!:\!S\!:\!O\;u,v\;O\;w_{1},w_{1}\;E\!:\!S E\!:\!S\;v,}}\\ {{v\;O\;w_{2},w_{2}\;E\!:\!S E\!:\!S\!:\!O\;v,u\;O\;w_{2},w_{2}\;E\!:\!S E\!:\!S\;u\right\}}}\end{array}$$
$$(15)^{\frac{1}{2}}$$

A basic constraint is imposed to each pair of variables in {u, v} × {w1, w2} ∪ {w1, w2} ×
{*u, v*}. In particular, the constraints involving w1 are u O w1, w1 E : SE : S : O u, and v O w1, w1 E : SE : S v. It is clear that these constraints imply M(u) and M(v)
have the same upper left corner point as M(w1) does (see Figure 4(a) for illustration).

Similarly, M(u) and M(v) have the same upper left corner point as M(w2) does (see Figure 4(b) for illustration). So the first requirement is satisfied. Furthermore, because w1 E : SE : S : O u but w1 E : SE : S v, we know M(u) is not contained in M(v).

Similarly, we have M(v) is not contained in M(u). Therefore, the second requirement is also satisfied.

On the other hand, if (*a, b*) is an instance of p, then we can find c1, c2 such that
{a, b, c1, c2} is a solution of Np.

## 4. Consistency Checking Of Conjunctive Cdc Constraints

This section proves that consistency checking of possibly incomplete basic CDC network is an NP-hard problem. We achieve this by reducing the 3-SAT problem to the consistency checking problem **RSAT**(Bdir *∪ {∗}*). For each 3-SAT instance φ, we construct an incomplete basic CDC network Nφ in polynomial time, and show that φ is satisfiable if and only if Nφ is consistent.