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?

CodePudding user response：

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.