# existence of a permutation that satisfies order-constraints

I would like to know if there is a simple algorithm for checking the existence of a permutation that satisfies a number of order-constraints.

For example, suppose we have a set (1, 2, 3, 4, 5) and a number of constraints:

• 1 should be before 2
• 2 should be before 4
• 4 should be before 1

(which is of course infeasible).

Is there a simple algorithm for checking the feasibility of order-constraints? (that does not rely on lp-solvers)?

I do not have anything against Lp-solving, but i suspect that simpler algorithms are available.

• You may be interested in Contraint programming (which is not the same as linear programming, but a superset). in particular you are interested in the algorithm for constraint propagation of binary contraints. Try searching a bit these terms and you will find some notions about consistency and some general algorithms, and also some interesting special cases (e.g. propagation of the "all different" constraint, which makes use of the maximal matching problem). – Bakuriu Sep 12 '16 at 16:18