Question

Can I please get help with this question? Will upvote. thanks.

Problem 4. 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 "x, = x," and some disequality constraints, of the form “x, #x": Is it possible to satisfy all of them? For instance, the constraints x, = XX, = x3,x; = x, *, * x. cannot be satisfied. Give a polynomial time algorithm that takes as input of m constraints over n variables and decides whether the constraints can be satisfied.

Answer 1

PLEASE GIVE AN UPVOTE

Ans two graphs Greg = Cu, Eeg) and G heq = Cui Enea)- we construct oproewer Cij) e Eea if x = x; is where v{...} we have if xit x; is a constraint constrant and (i, j) E Enea must - since equality is an equivalence relation all the varibles in each connected component of Gea have the same value. The system of constraints satisfiable it and only if there is no edge (isi) Same component Enea Such that -x, and xy are the Gea. The decomposition in components and in polynomial both be done Checking for edges can time