Complexity of solving a system of difference constraints with variables restricted to a finite set

Santiago Cifuentes, Francisco J. Soulignac, Pablo Terlisky

Fishburn developed an algorithm to solve a system of $m$ difference constraints whose $n$ unknowns must take values from a set with $k$ real numbers [Solving a system of difference…