Motivation
Bellman-Ford is an algorithm for finding shortest paths from a single source vertex to multiple target vertices in a weighted graph \(G(V,E)\) whose edge weights can be negative. The algorithm can also detect negative cycle (if any) in the graph. Its time complexity is \(O(|V|*|E|)\).
This post is, however, about a lesser-known application of the algorithm, namely solving a system of difference constraints of \(n\) variables \(\{x_i\}_{i=1}^n\) and \(m\) constraints of the form: \(x_j - x_i \leq w_{ij}\), in \(O(m*n)\) time complexity.
- Note that this problem can be formulated as \(A x \leq w\), in which \(x\) is the \(n\)-vector of \(\{x_1,...x_n\}\), \(w\) is the \(m\)-vector of corresponding constraints, \(A\) is a \(m \times n\) matrix such that each row contains exactly one 1 and one -1 and 0 otherwise. We need to either find \(x\) satisfies the inequality, or report that no solution exists, i.e., the constraints are unsatisfiable!
Wait a minute, I want a real-world problem, not a toy, theoretical one! Sure, you can find systems of difference constraints in many practical problems. For example, consider task scheduling with precedence constraints, in which we have \(n\) tasks,
- \(x_i\) is the starting time of the \(i^{th}\) task
- constraints: a task \(i\) needs to be finished before starting a task \(j\), i.e., \(x_i + \text{duration}(i)\leq x_j \Rightarrow x_i - x_j \leq -\text{duration}(u)\)
Also, it turns out we can find a solution that minimizes the spread of time of all tasks \(\max_i x_i - \min_i x_i\) with the algorithm described below.
Another example is in VLSI layout design, making chip layout as compact as possible while keeping required distances between components for reasonable performance.
Convinced? So let's dive in!
Observation
Following are key observations, which suggest surprising connection between the shortest-path problem and the system of difference constraints:
- \(x_j - x_i \leq w_{ij} \Rightarrow x_j \leq x_i + w_{ij}\)
- recall the relaxation often used in the shortest-path problem, \(d_i, d_j\) are the shortest path from the source \(s\) to vertices \(i, j\) respectively, \(w_{ij}\) is the weight of edge \(i \rightarrow j\) (assume existed), then \(d_j \leq d_i + w_{ij}\)
Constraint graph
Let's convert the system of difference constraints into a graph:
- \(n\) vertices corresponding to \(n\) variables \(\{x_i\}_{i=1}^n\)
- for each constraint \(x_j - x_i \leq w_{ij}\), add an edge \(i \rightarrow j\) with weight \(w_{ij}\). There are \(m\) edges in total.
The resulting graph is the constraint graph corresponding to the original system of difference constraints.
Claim 1: If there exists a negative cycle in the constraint graph, then the original system is unsatisfiable
Assume there exists a solution to the original system and a negative cycle \(x_1 \rightarrow x_2 \rightarrow ... \rightarrow x_k \rightarrow x_1\), i.e., \(w_{12} + ... + w_{k1} < 0\). However, \(w_{12} + ... + w_{k1} = x_2 - x_1 + ... + x_1-x_k = 0\). This is contradiction, hence Claim 1 is proved.
Here comes Bellman Ford algorithm, helping us detect if any negative cycle in the constraint graph. If there is, then Claim 1 tells us that the system is unsatisfiable.
Extend the constraint graph
Here we assume no negative cycle in the constraint graph (judged by Bellman Ford algorithm), then how can we find a solution to the constraint system?
The key idea is to add a new vertex \(s\) to the constraint graph and \(n\) edges of weight 0 from \(s\) to all existing vertices.
Adding weight-0 edges to the graph doesn't introduce any negative cycle, and guarantee there are shortest paths from \(s\) to all \(n\) vertices \(\{x_i\}_{i=1}^n\). Let \(\{d_i\}_{i=1}^n\) denote the corresponding shortest distances.
Claim 2: \(\{d_i\}_{i=1}^n\) satisfies the difference constraints, and thus is a solution of the original system
This is mostly obvious given the triangle inequality (aka relaxation constraint) \(d_j \leq d_i + w_{ij}\).
Algorithm
To solve a difference constraint system, we can just:
- Construct the corresponding constraint graph, extended with a source vertex \(s\) (as mentioned above)
- Then run Bellman-Ford on the resulting graph to obtain shortest distances from \(s\) to the remaining vertices
- If a negative cycle is detected, report no solution
The time complexity of this algorithm is \(O(m*n)\), thanks to the Bellman-Ford algorithm.
Implementation
See my simple implementation of the Bellman-Ford algorithm.
Remark
There are cool properties of the solution found by the Bellman-Ford algorithm, which are worth mentioning:
- minimizes \(\max_i x_i - \min_i x_i\), i.e., it minimizes the spread of the solution. This is useful, for example, consider the task scheduling problem at the begining. The algorithm essentially minimizes the time to complete all tasks while satisfying all scheduling constraints.
- maximize \(\sum_{i=1}^n x_i\) given addition constraints that \(x_i \leq 0\) for all \(i\).