2

Given a set of variables and a set of strict inequalities, it's straightforward enough to detect whether there is an inconsistency: make a directed graph whose nodes are variables; for each assertion a > b add an edge from a to b and vice versa for a < b; check whether there are any cycles in the graph.

However, this does not suffice for non-strict inequalities; the above algorithm doesn't handle the case where you have some assertions a = b.

What's the simplest algorithm to detect inconsistency in a set of non-strict inequalities?

rwallace
  • 31,405
  • 40
  • 123
  • 242

1 Answers1

4

This way works:

  1. Replace every x=y with x>=y and y>=x
  2. Create a directed graph among the variables with, with a green edge from x to y if x>=y, and a red edge from x to y if x>y
  3. Determine the strongly connected components of the graph, using e.g., Tarjan's algorithm
  4. If there is a red edge within any SCC, then the set of equations is inconsistent.

The way this works is simple: In any cycle of >= edges, all the variables must be equal, but that's not possible if one of those edges requires that they are not equal.

Matt Timmermans
  • 53,709
  • 3
  • 46
  • 87