Given two connected weighted graphs and a set of pairs of vertices that can "cross the river" between the two graphs, the task is to find an MST (minimum spanning tree) of a graph made of both graphs connected with the crossings that contains exactly N crossings over the river. The solution to a given arrangement always exists.
In the example below, the left graph has vertices (0, 1, 2, 3) and the right one (4, 5, 6, 7, 8). The edges 3-4, 3-5, 2-4, 2-5 are to be chosen from and N = 2. The minimum spanning tree that contains exactly two crossings over the river is depicted in red.
First of all by the cut property of MSTs, I think that the crossings to be chosen are the N lowest ones.
Secondly, how do you force, say Primm's algorithm to choose some edges when trying to find an MST? You can't just connect the chosen crossings beforehand as it will probably choose just one.
First, my idea was to modify it such that it always chooses the chosen crossings (3-5 and 2-4 in the picture above) during the process, but that could create a loop, right? It has to somehow know not to create a loop when forcefully chosing some vertices.
My second idea was to find MSTs for the left and the right side and only then try to connect them - wouldn't that possibly create a loop though? What if you just break the loop with the largest value edge? Wouldn't that automatically yield the answer? You would have it assurred that both sides have their MSTs, those are connected with the cheapest paths and there is no cycle.
Here’s an algorithm that’s simpler than weighted matroid intersection. Letting C be the set of crossing edges, it runs in time O((|E| + k |C|) log |V|) assuming an efficient implementation using dynamic trees. (I’m sandbagging the running time a bit; you could use a better initialization algorithm than Prim or Kruskal.)
The problem is:
Except for the constraint marked (*), this is a classic minimum spanning tree problem. Let’s reformulate (*) using a Lagrange multiplier, λ.
Intuitively, we choose x, and an adversary responds by choosing λ. If we choose fewer than k crossing edges, then the adversary trashes the objective as λ → −∞. If we choose more than k crossing edges, then the adversary trashes the objective as λ → ∞. Thus it behooves us to choose exactly k crossing edges.
This problem has a dual problem:
Here the adversary chooses λ, and we respond by choosing x. Intuitively, this should be strictly better for us, but for interesting mathematical reasons, with perfect play, it’s exactly the same. Now, the trick is that we can take the multiplier λ and fold its contribution (except for λ k, which is constant in x) into the weights w, giving us back a standard minimum spanning tree problem.
Algorithm
This is a kinetic algorithm. Initialize it with a minimum spanning tree, considering the edges of E ∖ C from lightest to heaviest followed by the edges of C from lightest to heaviest. This is the minimum spanning tree in the limit as λ → ∞. If it has more than k crossing edges, then there is no solution; this spanning tree has as few crossing edges as possible. We maintain the minimum spanning tree as we slide λ towards −∞, stopping when either there are exactly k crossing edges (optimal solution) or we reach the limit (no solution).
As usual, we don’t literally change λ by small increments. Instead, we look for the next value of λ where “something interesting happens”, i.e., find the maximum λ such that there exists an edge e ∈ C not in the current spanning tree and an edge e′ in E ∖ C in its fundamental cycle such that w(e) + λ = w(e′). We remove e′ from the spanning tree in favor of e. Data-structurally, a dynamic tree is (in theory) an efficient way to make these operations fast. For at most k times, we loop over e ∈ C and make an O(log |V|)-time query for each one, followed by two O(log |V|)-time topological changes.