2
$\begingroup$

It is known that that can be several trees in a graph that follow the conditions of "Cut-tree" (also called Hu-Gomory tree).

For example (https://stackoverflow.com/questions/25297470/igraphs-gomory-hu-tree-not-working) In V={1,2,3}, E={{1,2},{2,3},{1,3}}, w({1,2}) = w({2,3})=1, w({1,3}) =0, all 3 possible spanning trees may are legal cut-trees.

In an article from 1974 it is stated that Hu-Gomory tree is an optimal communication tree https://epubs.siam.org/doi/pdf/10.1137/0203015 in the case of all distances equal to 1.

But in the graph i showed, only ({1,2},{2,3}) is optimal communication tree (with sum communication of 2), and other trees with sum communication of 3. How is this possible? Am i missing something?

Thanks

$\endgroup$

1 Answer 1

2
$\begingroup$

Taking the definition of a cut-tree from the linked paper (page 190, just before Lemma 1), or equivalently, the definition of a Gomory-Hu tree from Wikipedia, it appears that the answer in the linked stackoverflow answer is not correct. For your example, using the Wikipedia notation, $\lambda_{12}=\lambda_{13}=\lambda_{23}=1$. Now take the tree $T$ with edges $\{1,2\}$ and $\{1,3\}$. For $s=1$ and $t=2$, the $s$-$t$-path in $T$ contains only the edge $e=\{1,2\}$ which induces the cut $(S_e,T_e)$ with $S_e=\{1,3\}$ and $T_e=\{2\}$. The capacity of this cut is $2$ which is not equal to $\lambda_{12}=1$, and therefore $T$ is not a Gomory-Hu-tree. The same argument applies to the tree with edges $\{1,3\}$ and $\{2,3\}$, so for your example $\{\{1,2\},\{2,3\}\}$ is indeed the unique Gomory-Hu tree.

$\endgroup$
0

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.