4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – D.W. May 10 '16 at 23:21
  • $\begingroup$ 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). $\endgroup$ – D.W. May 10 '16 at 23:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.