For a given undirected graph $G$, a Gomory-Hu tree is a graph which has the same nodes as $G$, but its edges represent the minimal cut between each pair of nodes in $G$. The Gomory-Hu algorithm finds such a tree for a graph. A representant pair of nodes is defined as follows: if $R$ and $S$ are two components of the Gomory-Hu tree, and there is an edge $e$ between them, then the nodes $r \in R$ and $s \in S$ are representants if the weight of the edge $(r,s)$ is the same as the weight of $e$.

I have to learn not only the algorithm, but also all the lemmas needed to prove that it works. For this specific lemma, there is a proof given in my learning materials, but I am afraid I don't understand how it works.

It starts by picking two components of the Gomory-Hu tree, $A$ and $B$, with an edge $h$ between them, $a \in A$ and $b \in B$ being the representants. In the next iteration, nodes $x$ and $y$ in $A$ are picked, and a new minimal $(x,y)$-cut is calculated (dividing $A$ into the subsets $X$ and $Y$), such that now $h$ connects $X$ and $B$. If $a \in X$, then $a$ and $b$ are still representants. But if $a \in Y$, the proof claims that $x$ and $b$ are the new representants of $h$.

For this, it states that

The cut which created $h$ divides $x$ and $b$. From that, it follows that $f(x,b) \le f(a,b)$.

[It uses $f(a,b)$ to denote the flow in the minimal cut between nodes $a$ and $b$.] Then it goes on to prove that also $f(x,b) \ge f(a,b)$. And then the two flows must be equal, so the flow between $x$ and $b$ is the same as the flow in the minimal $(a,b)$-cut, so $x$ and $b$ are representants.

But as I understand the algorithm, the cut which created $h$ was a minimal cut between the nodes $a$ and $b$. The node $x$ wasn't even a special node at the time the graph was divided into components $A$ and B$.$ Yes, this cut happens to divide $x$ and $b$ too, but there is no guarantee that it is the minimal cut between $x$ and $b$ (this is exactly what we are trying to prove here). So I think that we can follow that $f(x,b) \ge f(a,b)$, but not that $f(x,b) \le f(a,b)$. I suspect that there is an error in my reasoning and not in the reasoning of the prof who wrote the learning materials, but where is it?

And if there actually is an error in this proof, what is the correct proof?

  • 1
    $\begingroup$ This question is cross-posted from math.stackexchange, as it has no answres and low view counts there. $\endgroup$ – rumtscho Jun 1 '12 at 15:46
  • $\begingroup$ @gilles yes, that's the same question. I tried to ask you mods if I should change the formulation of the question for this site, but you weren't online then. $\endgroup$ – rumtscho Jun 1 '12 at 20:08
  • 2
    $\begingroup$ Generally it's preferred that the question be migrated, but reposting a question that's been on another site for a while and hasn't been satisfactorily answered is ok. You really should link the two questions though, so someone finding one can easily go and see if the other one has been answered. $\endgroup$ – Gilles 'SO- stop being evil' Jun 1 '12 at 20:11
  • $\begingroup$ I think if in your reference author write "The cut which created $h$ also divides $x$ and $b$." was more clear, but to be more clear, note that, in s-t cut, you will divide your graph into two parts, also note that in this case one part of your s-t cut contains nodes $x$ and $a$ and ... (a component which contains those elements), so if $h$ disconnects $a$ from $b$, $h$ also disconnects $x$ from $b$ because $x$ was in $a$ side (bride side;). Now you can claim that $f(x,b) \le f(a,b)$. $\endgroup$ – user742 Jun 2 '12 at 9:03

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.