Algorithms: Difference Constraints

Question

I'm currently studying for my algorithms final and I came across a practice problem that I can't seem to figure out. Here's the problem:

Consider the following set of difference constraints:

x1 - x4 <= 1  
x2 - x1 <= 2  
x2 - x4 <= 0  
x3 - x1 <= 1  
x4 - x1 <= -1  
x4 - x3 <= -2  

What is the solution that will be provided by the shortest path based algorithm for this set of constraints?

I know that you are supposed to create a graph using these constraints, so that there is one edge per constraint and one node per variable. So, for this problem, there would be four nodes: x1, x2, x3, and x4. There would also be six edges because there are six constraints. The first constraint should make an edge from x4 to x1 with a weight of 1. The second constraint should make an edge from x1 to x2 with a weight of 2. The rest of the constraints are made into edges following the same pattern.

So after you create the graph, you're supposed to run a shortest path algorithm on it, and it somehow gives you the values for each variable. This is the part that I am unsure about.

The answer that I got when I did this was that x1 = 0, x2 = -1, x3 = 0, and x4 = -2. Unfortunately, this doesn't work because of the first and third constraints.

Can someone walk me through how to get the right answer using the shortest path based algorithm for this question? Thanks!

Answer 1

I think what you ask for is the AOE (Activity on edge) network, which is a popular tool for project management. Each $x_i$ is a check point, and an arc (directed edge) $(x_i,x_j)$ of weight $w_{ij}$ means there is an activity which takes $w_{ij}$ time and can only start after we reach $x_j$. You can rewrite all the constraints in the form $x_j\geq x_i+w_{ij}$.

Usually we add a dummy source with zero-weight arc to all $x_i$ of in-degree zero and a dummy sink with zero-weight arc from all vertices of out-degree zero. The graph must be a dag (directed acyclic graph), or otherwise there is no solution. Then we can find for each vertex the longest path length from source, which is the so-called earliest starting time. All the earliest starting times form a feasible solution (values of $x_i$). A critical path is a longest path from the source to the sink, and the path length is the minimum total time we can complete the project.

BTW, finding single-source all-destination longest paths can be easily done in linear time, using a standard dynamic programming. (I think the textbook of data structure by Horowitz and Sahni contains this topic)

Answer 2

You seem to already know the correct procedure but you have calculated the shortest paths incorrectly.

Procedure:

1. Create a source vertex ($s$) and add zero-weight edges from the source to all vertices.
2. Compute single-source shortest path from the source to each vertex. (If a negative-weight cycle exists, there is no solution to the set of constraints.)
3. The constraints are solved by assignments $x_i = \delta(s, x_i)$ where $\delta(s, x_i)$ is the shortest path from $s$ to $x_i$.

x1 = -1 (s -> x3 -> x4 -> x1)
x2 = -2 (s -> x3 -> x4 -> x2)
x3 =  0 (s -> x3)
x4 = -2 (s -> x3 -> x4)

Source: See slides 6-10 of http://courses.csail.mit.edu/6.006/spring11/lectures/lec17.pdf