Here's a problem that occurs in automatic program analysis. For a set of variables x1; : : : ; xn, you are given some equality constraints, of the form xi = xj and some disequality constraints, of the form xi 6= xj . Is it possible to satisfy all of them?

For instance, the constraints x ₁ = x ₂ ; x ₂ = x ₃ ; x ₃ = x ₄ ; x ₁ 6= x ₄ cannot be satisfied. Give an efficient algorithm that takes as input m constraints over n variables and decides whether the constraints can be satisfied.

Answer rating: 100% (QA)

2 Polynomialn a For i is 1 to n b do if xjxi1 c then satisf... View the full answer