Question

Here's a problem that occurs in automatic program analysis. For a set of variables x1, x2, ..., In, you are given some equality constraints of the form "Xi = x;" and some disequality constraints of the form "r; # x;". Is it possible to satisfy all of them? For instance, the constraints Xi = x2, 22 = x3, x3 = 24, X1 + x4 cannot be satisfied. Give an efficient algorithm that takes as input m constraints over n variables and decides whether the constraints can be satisfied.

Please do not copy-paste an existing answer.

Answer 1

SOLUTION :-

Assume that G = (V, E) is a graph that has following properties :
G is having a node corresponding to each variable x_i , and there is an edge (x_i, x_j ) if x_i = x_j is an equality constraint. Now perform Depth First Search of G in order to find all its connected components. For every node x_i , if it is in the p-th connected component of G, then allocate it a mark p.
Now for every disequality constraint x_i ≠ x_j , Examine to view if x_i and x_j occur in distinct connected components of G. If there is few disequality constraint x_i ≠ x_j such that x_i and x_j occur in the same connected component of G, then It means that the constraints are unsatisfiable. If there is no such constraint exists, then it means that the constraints are satisfiable.

Correctness of the above algorithm :-

In the above problem, the equality constraints formulates an equivalence class. If all the constraints are satisfiable, then, there can be no disequality constraint x_i ≠ x_j such that x_i and x_j are in the same equivalence class, it is because such a constraint is not satisfiable, which directs towards contradiction. Thus, if all the constraints are satisfiable, then the algorithm will perform in a correct manner.

Now assume that all the constraints are not satisfiable, we claim that it can only occur if there is an disequality constaint x_i ≠ x_j where x_i and x_j lie in the same equivalence class. Assume that it is not the scenario, and that for all disequality constraints x_i ≠ x_j , x_i and x_j lie in distinct connected components. Then, an assignment that allocates a value p to all the variables in connected component p satisfies all the constraints, therefore directing towards a contradiction. Thus, if all the constraints are not satisfiable, then, the algorithm performs in a correct manner.

=======================================================================