Solving a in/equality constraint problem with graph search

Question

You are given a list of m constraints over n distinct variables x1, ..., xn. Each constraint is of one of the following two types.

1. An equality constraint of the form xi = xj for some i!=j.
2. An inequality constraint of the form xi!= xj for some i!=j.

I want to find an assignment, if it exists, for each variable such that it conforms to all the constraints using a graph search algorithm in O(m+n) time.

This reminds me of the graph colouring problem, however that only involves checking graph neighbours where as in any efficient graph I could think of, the nodes sharing a constraint may not be neighbours.

My first thought was to create a graph such that all nodes that equal are connected then use DFS to traverse each node and check if it has an inequality with a parent, however that doesn't seem very efficient as for every node (m) I have to traverse every inequality constraint (at most n) which brings me to nm time, where as DFS inherently has O(m+n)on an ideal representation.

Any clues?

Answer 1

You're on the right track. Construct an undirected graph with an edge for each equality constraint, as you suggested. Next, look into the concept of connected components, and algorithms for finding them. You should be able to take it from here.

This problem can be solved in linear time.

Answer 2

Let there be K equalities.

1. Create a forest of n nodes stored in an adjacency list O(n)
2. For each equality between Xi and Xj, add an edge between them. O(2k)
3. Call DFS on any node. O(|m| +|n|)
   1. DFS has a counter that starts at 0
   2. When DFS visits a node it sets that node’s value to the current value of its counter
   3. When DFS crosses a cross-edge, it increments it’s counter by 1
4. For each inequality between Xi and Xj, check their values assigned by the counter during the DFS, if they are equal return NIL O(2(m - k))
5. Create the result array by going through the adjacency list and setting the value at index j of the node X_j O(n) => Worst case time complexity O(3|m| + 3|n|) => O(|m| + |n|)