0
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Your problem is far from well-defined. Can you give a complete and non-trivial example? Can you tell us what motivated you to create the problem? We might be able to help you identify what could be an interesting problem. $\endgroup$
    – John L.
    Mar 19, 2019 at 21:13
  • $\begingroup$ @Apass.Jack hope I clarified it in my last edit. $\endgroup$
    – donkey
    Mar 20, 2019 at 16:16

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ How would you suggest dealing with conflicting constraints? $\endgroup$
    – donkey
    Mar 21, 2019 at 16:26
  • $\begingroup$ @Ge0rges, I suggest spending some time on the problem. A useful approach is to pick a small example, then try to work through it by hand (construct the graph of equality constraints, find the connected components, then figure out what to do with the inequality constraints); and do it for a few examples. Maybe pick some examples with conflicting constraints and some without. Looking at specific small examples should help you figure out what makes sense to do. If after that, you're still stuck, show us your progress and thoughts so far and ask about what you're stuck on. $\endgroup$
    – D.W.
    Mar 21, 2019 at 16:38
0
$\begingroup$

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|)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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