CMP.1:5.1 - Solve difference constraints through a graph problem

The input is a finite set of variables and inequalities of the form:

x_v <= x_u+w(u,v),

with rational weights. The required answer is an assignment satisfying all inequalities or a correct infeasibility report.

Construct a directed graph with one vertex per variable and an edge u to v of weight w(u,v) for each inequality. Add a new source s with a zero-weight edge to every variable vertex. Use a solver that permits negative edge weights and returns either shortest-path distances from s or a reachable negative cycle.

A negative cycle proves infeasibility: sum its inequalities. Every variable cancels, leaving 0 <= sum of cycle weights, which is false for a negative total.

If there is no negative cycle, all vertices are reachable from s and their shortest distances are finite. For every edge, the shortest-path condition gives:

d(v) <= d(u)+w(u,v).

Thus x_v=d(v) recovers a satisfying assignment. This proves the required return for either solver outcome.

For example, take x_b<=x_a+3, x_c<=x_b-2 and x_a<=x_c+1. Distances (d(a),d(b),d(c))=(-1,0,-2) satisfy all three. If the final bound changes to x_a<=x_c-2, the directed cycle has weight 3-2-2=-1 and proves infeasibility.

For n variables and m inequalities, construction adds n+1 vertices and m+n edges. Reading or assembling those lists and copying back an assignment takes O(n+m) operations under the explicit-graph model. Add the selected solver’s cost on that graph and the rational-arithmetic costs appropriate to the representation.

The graph is a computational construction for the given inequalities. If those inequalities describe schedules, flows or another subject, their physical or organizational adequacy is a further modeling question. The reduction has established the answer for the supplied mathematical constraints.