1
$\begingroup$

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$.
  1. 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.

$\endgroup$
1
  • $\begingroup$ My idea: Split the variables into equivalence classes; xi and xj are in the same class if there is a "=" relation. For either relation xi ≠ xj check that xi and xj are not in the same equivalence class. The rest is implementation. $\endgroup$
    – gnasher729
    Sep 13 at 17:09

2 Answers 2

0
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Oh I see that now. Thank you for the response. Appreciate it! $\endgroup$ Sep 13 at 14:25
  • $\begingroup$ Wait, the updated algorithm may fail, too. For example, $x_1=x_3$, $x_2=x_3$. $\endgroup$
    – John L.
    Sep 13 at 14:48
  • $\begingroup$ Then again, why would the algorithm fail in the first place? In the given example I'd get $x_1=1,x_2=2,x_3=3$ and the case where $x_1\neq x_3$ would check out. $\endgroup$ Sep 13 at 14:51
  • $\begingroup$ @RamiHashan please check my updated answer. $\endgroup$
    – John L.
    Sep 13 at 16:16
  • $\begingroup$ Thanks a lot. The explanation was great! $\endgroup$ Sep 13 at 16:29
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you very much. We haven't learned Adjacency Lists in our course. Talking to the instructor he said that it is not possible to solve in $O(m+n)$ as asked in the question with our current knowledge. Now I see why. Nevertheless thanks for your response! $\endgroup$ Sep 13 at 18:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.