1
$\begingroup$

We have undirected connective, weighted graph $G = (V,E)$. we also know that for every $e,e'$ in $E$, $w(e)≠w(e')$. Prove that $G$ has a single MSP. Ideas?

$\endgroup$
2
  • $\begingroup$ Have you checked the proof in Wikipedia? $\endgroup$
    – xskxzr
    Nov 30, 2019 at 12:31
  • $\begingroup$ In fact, if the maximum-weight edge in any cycle of $G$ is unique, then $G$ has a single MSP, as shown here. For more comprehensive discussion on uniqueness of MSP, check this. $\endgroup$
    – John L.
    Dec 10, 2019 at 6:19

1 Answer 1

0
$\begingroup$

I missed the part where $\omega(e) \neq \omega(e')$ for $e\neq e'$ so please only consider my answer for the general case, i.e. Given a graph $G =(V,E)$ how to check if $G$ admits a unique MST.

The answer is based on the following claim.

Claim. An MST $T$ is unique, if and only if each edge $\{u, v\}$ not in $T$ has greater weight than all edges on the path in $T$ between $u$ and $v$.

Assuming for now that the claim is true, the task turns into checking for each edge $\{u, v\} \in E \setminus E(T)$, if the path in $T$ between $u$ and $v$ contains an edge with weight at least $w$. If this is the case the answer is No. If this is not the case for all edges not in the tree, output Yes.

Now we need an algorithmic approach to solve the previous problem. Naively, We start by building an arbitrary MST, then we can traverse the path for each such pair $u, v$, where $\{u, v\}$ is not in the tree. However, in a dense graph (say the complete graph $K_n$), this algorithm has running time of $\theta((n+e)\log n + n^3) = O(n^3)$ since we have $\Theta(n^2)$ edges not in the tree and the length of the path is linear. In the following we show how to do each check in $O(\log n)$ time instead achieving a better total running time.

The trick is to use LCA (lowest common ancestor), a data structure defined on rooted trees, that answers the following queries efficiently. Given a pair of vertices $u, v$ in the tree, find a vertex $w$ with the lowest height, such that $w$ is an ancestor of $u$ and an ancestor of $v$. Note that $x$ is an ancestor of $y$ if it lays on the path from the root of the tree to $y$. LCA can be built in running time $O(n \log n)$ answering queries can be done in $O(\log n)$. there are also better "theoretical" results using sparse-tables. However, this ones suffices our needs. We also need to tweak the data structure to answer queries of the form (what is the maximum weight of a vertex on the unique path from $u$ to $v$), note that this is doable by keeping more data about the tree while building the data structure. Also note the choice of the root in this case does not matter and you can choose any vertex to be root.

Now assuming a black-box is given (the LCA data structure) that in $O(\log n)$ time for two given vertices $u$ and $v$ finds the maximum weight of an edge on the path from $u$ to $v$ in the tree. We can do the following, for each edge $\{u, v\}$ not in the tree, call the black-box on $u, v$. If the answer is at least the weight of the edge, output No. If the answer is less than the weight for all edges not present in the tree, output Yes. The running time can be found as follows. We need $O((n+m)\log n)$ to build an MST. We need $O(n \log n)$ to build the LCA data structure (including rooting the tree and computing the depth and the parent of each vertex). We need $O(\log n)$ pro query totaling in $O(m \log n)$ for all queries. Hence a total running time of $O((n+m)\log n)$.

Now we still have to prove the claim presented in the beginning, namely that the tree is unique if and only if for each edge $\{u, v\}$ not in the tree, all the edges on the path between $u$ and $v$ in the tree have strictly smaller weight than the edge $\{u, v\}$.

Proof. Let $\omega: E \rightarrow R$ be the weight function. Assuming there is an edge $\{u, v\}$, such that the path in $T$ between $u$ and $v$ contains and edge $\{x, y\}$ where $w(\{u, v\} \leq w(\{x, y\})$. Then by removing $\{x, y\}$ from the tree adn adding $\{u, v\}$ we get a spanning tree of total weight at least as good as $T$ and hence an MST is not unique. Try to see why the resulting structure is a tree.

For the other direction, we prove the following claim. If there is a simple cycle $C$ where an edge $\{u, v\} \in C$ is heavier than all other edges in the cycle, then there is no $MST$ containing $\{u, v\}$ as an edge. Assuming there is such a tree, by removing $\{u, v\}$ from the tree, we get two connected components. One of the edges in the cycle (say $e'$) must also connect these two components (since cycles are 2-connected) and hence we can add $e'$ to build a strictly lighter MST, contradicting the claim that the given tree was an MST. Hence $\{u, v\}$ is not in any MST as claimed. Now complete the original proof, note that the path in the tree from $u$ to $v$ with the edge $\{u, v\}$ build a cycle. Hence, we output Yes if all edges not in the tree are heavy for some cycle and hence cannot appear in any minimum spanning tree.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.