Algorithm to find if there exists an assignment such that all equality and inequality constraints are satisfied

Question

I have a problem in a Data Structures course I am taking. The question is as follows:

Given a number of variables $x_1,\dots,x_n$ and given $m$ equality and inequality constraints (in total $m$ constraints). Find if there exists a valid assignment that satisfies all constraints in $O((m+n)\log^*n)$ and in $O(m+n)$.

For example $x_1=x_2,x_2=x_3,x_1\neq x_3$ doesn't have a valid assignment.

I believe this question is a known one but I can't find it's name or know what to search for.

My idea is:

1. Assign a $null$ value to all variables.
2. For each $1\le i \le n$:

• If $x_i=null$ then assign $x_i \leftarrow i$.
• Go over all of $x_i$ equality constraints and assign for each index $j$ the value $x_j \leftarrow x_i$.

3. Go over all of the inequality constraints and check if they hold. If at least one doesn't hold, return that there is no such valid assignment. If all of them hold return the current assignment that we have.

Using that algorithm we can guarantee that all equality assignment will be satisfied. Thus checking if the inequality assignments hold is enough to check if a valid assignment is possible.

Analyzing this algorithm. Let $m_i$ be the number of equality constraints on $x_i$ and let $m_i'$ be the number of inequality constraints. Therefore $\sum_{i=1}^{n}(m_i + m_i')=m$. The first step costs $n$ operations. The second step costs $\sum_{i=1}^{n} m_i$. The third step costs $m-\sum_{i=1}^{n} m_i$.

In total we get $n + (\sum_{i=1}^{n} m_i) + (m - \sum_{i=1}^{n} m_i)=n + m\in O(n+m)$.

I am not sure if this satisfies the second request of the question as I am not sure my calculations are valid. I would appreciate if someone can refer me to a source on this question or tell me if my calculation is correct. I would also appreciate if someone can help me offer a solution that'll take $O((m+n)log^*n)$.

Thanks in advance.

Answer 1

Your algorithm may fail in some situations.

For example, $x_1=x_2$, $x_2=x_4$, $x_3=x_4$, and $x_1\not=x_2$.

1. $i=1$, $x_1\leftarrow1$, $x_2\leftarrow1$.
2. $i=2$, $x_4\leftarrow1$.
3. $i=3$, $x_3\leftarrow3$, $x_4\leftarrow3$.
4. $i=4$, $x_2\leftarrow3$.

At the end, the only inequality $x_1\not=x_2$ is satisfied. So your algorithm will not report that "there is no such valid assignment".

---

For this exercise, you are supposed to use disjoint data structure.

Consider the set that contains $1,2,\cdots, n$. For $i$ from $1$ to $n$, let $\text{parent}(i)=i$.

Process all equalities first. For each equality $x_j=x_j$, join $i$ and $j$.

Then for each inequality $x_i\not=x_j$, check if $\text{find}(i)\not=\text{find}(j)$. If both sides are equal, return "there is no such valid assignment".

If the algorithm has not returned yet, return the assignment where $x_i\leftarrow \text{find}(i)$ for all $i$.

---

The algorithm runs in $O((m+n)\log^*n)$ time, assuming the $\text{find}$ operation is implemented properly.

Answer 2

To complement John L.'s $O((m+n)\log^*n))$ solution, here is a simple $O(n+m)$ time solution:

Construct the graph $G$ (as an adjacency list structure) whose vertices correspond to your variables and edges correspond to equality constraints. Compute the connected components of this graph and a an array which to each variable index associates a number corresponding to its component.

Now for each inequality constraint, check if the two variables are in different components of $G$. If that is always the case then there is a satisfying assignment (which is actually given by the array you computed), otherwise there isn't.