1
$\begingroup$

I'm not sure if my solution to the following problem (adapted from Exercise 20, Chapter 4 of Algorithm Design by Jon Kleinberg and Éva Tardos) is correct. I would appreciate it if anyone could point out any logical flaws in it.

The problem:

Let $G=(V,E)$ be a connected graph on $n$ nodes. Suppose each edge $e$ in the graph is annotated with a number $a_e$ (an "altitude"), and that no two edges have the same altitude. The height of a path $P$ in the graph is the maximum of $a_e$ over all edges $e$ on $P$. A path between two nodes $i$ and $j$ is said to be optimal if it achieves the minimum possible height over all paths from $i$ to $j$.

Let $E'\subseteq E$, and let $(V, E')$ be a connected subgraph. We say that $(V, E')$ is a minimum-altitude connected subgraph if for every pair of nodes $i$ and $j$, the height of the optimal path in $(V, E')$ is no greater than it is in the full graph $G=(V, E)$.

Prove that the minimum spanning tree of $G$, with respect to the edge weights $a_e$, is a minimum-altitude connected subgraph.

My solution:

Let $T$ be the minimum spanning tree of $G$ (it is unique because the edge weights are distinct). Assume for the sake of contradiction that $T$ is not a minimum-altitude connected subgraph. Then there exist nodes $v$ and $w$ such that the height of the $v-w$ path in $T$ is greater than the height of the optimal $v-w$ path in $G$. Denote the $v-w$ path in $T$ by $P_T$, its height by $h_T$, and the edge on $P_T$ with maximum altitude by $e_T$. Likewise, denote the optimal $v-w$ path in $G$ by $P_G$ and its height by $h_G$.

Consider the cut in $T$ defined by $e_T$, which partitions $V$ into two sets, one containing $v$ and the other containing $w$. Note that because $P_G$ is a $v-w$ path, it must contain an edge $e_c$ that crosses this cut. However, by the Cut Property, we know that $e_T$ is the crossing edge with minimum altitude, meaning $a_{e_c} \geq a_{e_T}$. Thus $P_G$ must contain an edge with an altitude at least as large as the altitude of the maximum-altitude edge on $P_T$. This contradicts our initial assumption that $T$ is not a minimum-altitude connected subgraph.

$\endgroup$
1
  • $\begingroup$ Welcome to CS.SE! We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – D.W.
    Jul 6 '21 at 22:40

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.