Building bridges problem - how to apply longest increasing subsequence?

Question

The building bridges problem is stated as follows:

There is a river that runs horizontally through an area. There are a set of cities above and below the river. Each city above the river is matched with a city below the river, and you are given this matching as a set of pairs.

You are interested in building a set of bridges across the river to connect the largest number of the matching pairs of cities, but you must do so in a way that no two bridges intersect one another.

Devise an algorithm to solve this problem as efficiently as possible.

I have heard that this problem is related to the longest increasing subsequence problem, but I don't see how to use it here. For example, if we're given the pairs

2  5  8  10
6  4  1  2

Then which sequence do we consider for LIS?

Thanks!

Answer 1

To build up to how you'd use the longest increasing subsequence algorithm to solve this problem, let's start off with some intuition and then build up to a solution. Since you can only build bridges between cities at matching indices, you can think of the set of bridges that you end up building as the largest set of pairs you can find that don't contain any crossing. So under what circumstance would you have a crossing?

Let's see when this can happen. Suppose that we sort all of the bridges built by their first city. If two bridges cross, then we must have that there is some bridge (a_i, b_i) such that for some other bridge (a_j, b_j) one of the following holds:

• a_i < a_j and b_i > b_j
• a_i > a_j and b_i < b_j

This first case says that there is a bridge whose top city is further to the right than the start of our bridge and whose bottom city is further to the left than the end of our bridge, and the second case handles the opposite case.

Given that this property needs to hold, we need to ensure that for every set of bridges, we have that exactly one of the two following properties holds for any pair of bridges (a_i, b_i), (a_j, b_j): either

• a_i ≤ a_j and b_i ≤ b_j

or

• a_i ≥ a_j and b_i ≥ b_j

In other words, if we were to sort the bridges by their first coordinate, the set of second coordinates would always be increasing. Similarly, if we were to sort the bridges by their second coordiante, the first coordinate would always be increasing.

The property that we've just defined defines a partial ordering ≤_both on the set of bridges, where we say that (a_i, b_i) ≤_both (a_j, b_j) if a_i ≤ a_j and b_i ≤ b_j. Notice that this is not a total ordering - for example, (1, 2) is incomparable with (2, 1) - but it is a partial ordering because it is reflexive, antisymmetric, and transitive.

Given this, the goal of the problem is to find the largest set of elements that we can that can be totally ordered by this relationship, since if we have a set containing two incomparable elements those elements must necessarily represent crossing bridges. In other words, we want to find the longest chain in the partial order. One way to do this is to, in O(n²) time, compare each element to each other element and see which elements can be ordered by ≤_both. This produces a directed acyclic graph, where the pair (a_i, b_i) has an edge to (a_j, b_j) iff (a_i, b_i) ≤_both (a_j, b_j). Once we have this directed acyclic graph, we can then find the longest path in the graph to find the largest set of elements that are call comparable by ≤_both, which then gives the solution to the problem. The overall runtime is thus O(n²).

However, we can do substantially better than this. The problem with the above algorithm is that we can't easily tell how the elements compare against one another, so we have to explicitly compare each city against each other city.

2  5  8 10
6  4  1  2 

Let's sort the cities by the bottom row:

8 10  5  2
1  2  4  6

Now, here's the really cool observation. If we have the elements sorted by their bottom row, then we can tell if two pairs are orderable by ≤_both by looking at their positions in the top row. If the first pair is to the left of the second pair, we immediately know that the second elements of the first pair is less than the second element of the second pair, since we've sorted them by the second coordinate. We then have that the pair of elements can be built together iff the first element of the first pair is less than the first element of the second pair. Consequently, if we want to find a set of bridges that can be built together, we're looking for an increasing subsequence of the top row, since in that case both the first and second elements of the pairs are increasing as we move from the left to the right. Finding the longest increasing subsequence then solves this problem. Since we can sort the pairs by their second field in O(n log n) and find the longest increasing subsequence in O(n log n), this is an O(n log n) solution to the problem!

Whew! Hope that this answer explains things in detail!