We are given a set V of n variables {x1, x2, ... , Xn} and a set C of m weak and strict inequalities between the variables, i.e., inequalities of the form Xi < x; or Xi < xj. The set C of inequalities is called consistent over the positive integers Z+ {1, 2, 3, ...} iff there is an assignment of positive integer values to the variables that satisfies all the inequalities. For example, the set {x1 < X3, X2 < x1} is consistent, whereas {x1 < x3, X2 < X1, X3 < x2} is not consistent.
Required:
a. Give an efficient algorithm to determine whether the set C of inequalities is consistent over the positive integers. State precisely the asymptotic running time of your algorithm in terms of n and m.
b. If the set of inequalities has a solution, then it has a unique minimum solution, i.e., a solution in which every variable has the minimum value among all possible solutions. Give an efficient algorithm to compute the minimum solution.
