Given two weighted, undirected graphs on $$$n$$$ nodes $$$G_1$$$ and $$$G_2$$$, is it possible to efficiently find a tree on these $$$n$$$ nodes that is an MST of both $$$G_1$$$ and $$$G_2$$$?
UPD: Building on chromate00's comments, it turns out that we can simply construct a new graph $$$G$$$ where the weight of each edge is the sum of that edge's weights in $$$G_1$$$ and $$$G_2$$$, and find the MST on this graph (in chromate00's notation here, this means we can actually just always set $$$C = 1$$$). If a common MST exists, we can guarantee that this algorithm will always find it.
Proof. Let $$$W_1$$$, $$$W_2$$$, and $$$W$$$ denote the total weight of MSTs for $$$G_1$$$, $$$G_2$$$, and $$$G$$$ respectively.
- Note that $$$W_1 + W_2 \leq W$$$.
- Also note that the weight of any spanning tree in $$$G_1$$$ is at least $$$W_1$$$, and similarly for $$$G_2$$$. Therefore, if we find a spanning tree $$$T$$$ with exactly $$$W = W_1 + W_2$$$, it must follow that $$$T$$$ has exactly weight $$$W_1$$$ in $$$G_1$$$ and exactly weight $$$W_2$$$ in $$$G_2$$$, since these are the minimum possible.
Here's a problem that uses this idea: 1054G - New Road Network
(This writeup is also available on my personal blog!)
Auto comment: topic has been updated by shsh (previous revision, new revision, compare).
Auto comment: topic has been updated by shsh (previous revision, new revision, compare).
This is what I have, it should be correct.
Construct graph $$$G = G_1 \cap G_2$$$, with weights $$$w_1 \cdot C + w_2$$$ where $$$C$$$ is some constant greater than $$$(\max w) \cdot n$$$ (This can be replaced with lexicographical order of pairs $$$(w_1,w_2)$$$ if you cannot find a usable value of $$$C$$$).
Now, compute a MST for this graph. There are three things that can happen:
If a MST for $$$G$$$ is a MST for $$$G_1$$$, it must have $$$\left\lfloor{\frac{W}{C}}\right\rfloor=\text{mst}_1$$$. And $$$\left\lfloor{\frac{W}{C}}\right\rfloor$$$ cannot be strictly less than $$$\text{mst}_1$$$, because then this construction is itself a contradiction of the MST of $$$G_1$$$. After fixing $$$\left\lfloor{\frac{W}{C}}\right\rfloor=\text{mst}_1$$$, it must now minimize $$$W \bmod C$$$ under the constraint. The only value this could have when a common MST exists is $$$W \bmod C = \text{mst}_2$$$. Also, we can show that the total weight of a spanning tree of $$$G$$$ cannot be strictly less than $$$\text{mst}_1 \cdot C + \text{mst}_2$$$. Therefore, when there is a common MST of $$$G_1$$$ and $$$G_2$$$, the MST of $$$G$$$ should be one, and its weight on $$$G$$$ must be $$$\text{mst}_1 \cdot C + \text{mst}_2$$$.
Oh, interesting! I had ruled out lexicographically ordering the pairs as a possible solution for some reason but now I see that it should still work. Would the proof be something like:
Maybe I had originally thought this was too simple to be correct, but it does seem to work!
Yes, that should be a good enough sketch for the proof.
By the way, do you have a link to any problems or resources about this idea? I couldn't find any online.
I haven't seen any problem that uses this idea. But either way, I think the idea is almost generalizable to any problem that can be modeled as a linear program (that is, for example given multiple weighted simple graphs, one can determine if there exists a path that is a shortest path for both graphs). That is, these kinds of problems belong to the category of multi-objective optimization, and what I have done is simply a way to solve lexicographic optimization problems out of them.
I see. For the weighted simple graph problem, would we just store for each node the lexicographically smallest pair $$$(d_1, d_2)$$$? And at the end, check whether our pair for the destination vertex matches the shortest path for both $$$G_1$$$ and $$$G_2$$$?
Also, are there any cases where such an approach fails?
Yes, that would work for the weighted simple path problem.
I don't know any case where such an approach fails if the two instances of problems that we want to solve are independent. That is, such an approach might fail if the two problems that we want to solve are interdependent (i.e. maybe what if we want to find two disjoint spanning trees for which one is a MST for $$$G_1$$$ and the other is a MST for $$$G_2$$$?), though at the same time I don't know any way to solve such problems efficiently.
By the way, I'm pretty sure it always works to just set $$$C = 1$$$; I've edited the blog with a proof of this, as well as a cool problem that uses this idea.
its ALL OVER THE SCREEN when shsh posts a blog
Auto comment: topic has been updated by shsh (previous revision, new revision, compare).
Auto comment: topic has been updated by shsh (previous revision, new revision, compare).
Auto comment: topic has been updated by shsh (previous revision, new revision, compare).