2
$\begingroup$

Given an undirected graph $G=(V,E)$ a Gomory-Hu tree $T$ for $G$ has the following properties:

  • $T$ has a node for each vertex in the graph G and each edge in the tree corresponds to a minimum cut separating the corresponding pair of vertices of G.
  • $T$ has the property that the minimum cut between vertices $s$ and $t$ in $G$ is the cut corresponding to the minimum weight edge along the path from $s$ to $t$ in the Gomory-Hu tree.

In $[1]$, the author states the following lemma:

Let $S$ be the union of cuts in $G$ associated with $n$ edges of $T$. Then removal of $S$ from $G$ leaves a graph with at least $n+1$ components.

Consider a complete graph $K_4$ with all the edges having weight $1$.
A (possible) Gomory-Hu Tree $T$ for $K_4$ is the following:

If we remove the cuts associated with all the $n=3$ edges of $T$ we might proceed as follows:

  • $(3,0) \in T$ $\rightarrow$ remove $\{(3,0),(3,1),(3,2)\} \in G$
  • $(3,1) \in T$ $\rightarrow$ remove $\{(3,0),(3,1),(3,2)\} \in G$
  • $(3,2) \in T$ $\rightarrow$ remove $\{(3,0),(3,1),(3,2)\} \in G$

A potential result (among the different ones) is a graph with $2 \neq (n+1=4)$ connected components, i.e., $\{3\}$ and $\{1,2,4\}$.
So, my question is, am I missing something in the definition or properties of the Gomory-Hu trees?
Does the author mean that for each $(u,v)$ in $T$, all the minimum weight cuts between $u$ and $v$ in $G$ should be removed in order for the lemma to hold?


[1] Vazirani, Vijay V. Approximation algorithms. Springer Science & Business Media, 2013

$\endgroup$
1
  • $\begingroup$ When you are saying "union of cuts", does it mean "union of cut sets"? Meaning of Cut-set: the set of edges that goes across the cut. $\endgroup$ – Inuyasha Yagami Jan 10 at 20:13
1
$\begingroup$

The book states the following definition of a cut:

a cut is defined by a partition of $V$ into two sets say $V^{l}$ and $V \setminus V^{l}$ and consists of all edges that have one endpoint in each partition.

Therefore, removing a cut from the graph should mean that we are removing the edges that go across the cut.

Also, consider the following definition of the "cut associated with an edge $(u,v) \in T$ in $G$".

Each edge $(u,v)$ in $T$ denotes a partition of $V$ given by the two connected components obtained by removing $(u,v)$ from $T$. Consider the cut defined in $G$ by this partition. We will say that this is the cut associated with $(u,v)$ in $G$.

Now, let us consider your example of Gomory-Hu tree for $K_{4}$. We want to find the cut associated with the edge $(3,0) \in T$. If we remove $(3,0)$ from $T$, we obtain the partitioning $\{1,2,3\}$ and $\{0\}$. This defines the cut in $G$. Therefore, you should be removing the edges of $G$ that goes across this cut i.e., $(0,1)$ $(0,2)$ and $(0,3)$.

Similarly for the edge $(3,1) \in T$, you should be removing the edges: $(1,0)$, $(1,2)$, and $(1,3)$.

And, for the edge $(3,2) \in T$, you should be removing the edges: $(2,0)$, $(2,1)$, and $(2,3)$.

It means we are removing all edges from the graph. Therefore, the number of connected components in the remaning graph would be $4 = (n + 1)$, for $n = 3$.

$\endgroup$
1
  • 1
    $\begingroup$ Nice, I had totally missed the definition of cut associated with (𝑢,𝑣) in 𝐺. $\endgroup$ – abc Jan 10 at 20:47

Your Answer

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

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