I have $n$ variables $x_1,\dots,x_n$.  I'm given a set $E$ of equalities (each of the form $x_i=x_j$ for some $i,j$) and a set $I$ of inequalities (each of the form $x_i \ne x_j$ for some $i,j$).  I want to find a maximum-size subset $E' \subseteq E$ such that $E'$ is compatible with $I$, i.e., such that there is an assignment to the $n$ variables that satisfies every inequality in $I$ and every equality in $E'$.Is there an efficient algorithm for this?I can see that the greedy algorithm (try adding equalities to $E'$ as long as doesn't imply the negation of some inequality) doesn't yield an optimal solution.  I have no idea what other approaches to try.Equivalently, the problem can be formulated in graph-theoretic terms.  I'm given an undirected graph $G=(V,E)$ and a set $I \subseteq V \times V$.  I want to find a maximum-cardinality subset $E' \subseteq E$ of edges, such that when I decompose the graph $G'=(V,E')$ into connected components, $v,w$ are in different connected components for all $(v,w) \in I$.
Maximum set of equalities, subject to some inequalities
algorithms;graphs;constraint programming;connected
Using your graph theoretic formulation, this problem can be restated as the multi-cut problem.Given a graph $G = (V, E)$ and a set of pairs $(s_i, t_i) \in I$ find a  set of edges $E' \subseteq E$ such that there is no path $s_i \leadsto t_i$ in the resulting graph $G' = (V, E \setminus E')$ for each $i$.Since each inequality is unweighted you need to find a minimum size multi-cut.This problem is NP-hard in general however there exist reasonable approximation algorithms that solve an LP. However a simple strategy might be to just take the union of each $(s_i, t_i)$ cut.