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?
This way works:
x=y
with x>=y
and y>=x
x
to y
if x>=y
, and a red edge from x
to y
if x>y
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.