Finding common MSTs
Given two weighted, undirected graphs on nodes and , is it possible to efficiently find a tree on these nodes that is an MST of both and ?
It turns out that we can simply construct a new graph where the weight of each edge is the sum of that edgeβs weights in and , and find the MST on this graph. If a common MST exists, we can guarantee that this algorithm will always find it.
Proof. Let , , and denote the total weight of MSTs for , , and respectively.
- Note that .
- Also note that the weight of any spanning tree in is at least , and similarly for . Therefore, if we find a spanning tree with exactly , it must follow that has exactly weight in and exactly weight in , since these are the minimum possible.
Hereβs a problem that uses this idea: 1054G - New Road Network
Hint
How can we reframe the problem as finding a simultaneous MST for graphs?
Solution
For convenience we will use MST = maximum spanning tree, but all the same principles still apply.
For the th community, let be the weighted complete graph in which edge has weight 1 if both and are in the th community, and weight otherwise. Then, it is necessary and sufficient that the final tree be a MST (maximum spanning tree) of . Therefore, we want to find a simultaneous MST over all .
From here, we easily arrive at the MST solution given in the official editorial by creating a new graph that sums edge weights across all and finding its MST.