# MST that contains a shortest $s,t$-path

Consider the problem in which we have an (undirected) graph $G=(V,E)$, weight function $w:E\to\mathbb N$ and a pair of vertices $s,t\in V$, and are required to determine whether there exists an MST $T$ such that $dist_T(s,t)=dist_G(s,t)$, i.e., $s$ and $t$ are connected by a shortest path.

How would you approach this problem?

Note: it seems that if there is only a single shortest path, we could simply reduce the weight of each of its edges by $1/n^2$ and find a simple MST. However, this doesn't seem to work when there are many short paths.

A generalization of the problem which is also interesting would be getting a set of terminal pairs $\{s_i,t_i\}_{i=1}^k$ which are required to be connected by a shortest path in the MST. This variant might prove to be NP-hard.

• Can you say anything about the context where you encountered this or the motivation? Is this an exercise you encountered somewhere? Is there a practical application? – D.W. May 10 '16 at 23:21
• 1. WLOG I think you can assume no edges have zero weight (otherwise contract them). 2. You can characterize the set of shortest paths as follows: there's a (directed) subgraph of $G$, call it $G'$, such that $p$ is a shortest path from $s$ to $t$ in $G$ iff it is a path in $G'$, and vice versa; in fact, $G'$ is a dag. I don't know if there's a similarly nice characterization of MST's that might be helpful here (one fact that could be useful is that the multiset of edge weights is the same for all MST's). – D.W. May 10 '16 at 23:31