Last TheoryLunch at Weizmann - Cut Equivalent Trees
1 Last TheoryLunch Meeting at Weizmann Institute of Science
For those of you who don’t know, this blog originated from my lunch meetings with my friends at Weizmann Institute of Science during my Master studies. As all good things comes to an end, also did my time at Weizmann, and last week our lunch group gathered for the last time. This post presents the topic discussed on that meeting.
I want to thank my good friends, Yosef Pogrow and Ron Shiff, for the great time we had and for all the enriching lunch meetings (also those which didn’t include theory). Without you guys, this blog would not have been created, I wish you both best of luck ahead!
This post, by the way, contains some results from the research of Yosef Pogrow (who also presented most of the meetings).
2 Min-Cuts in a Graph
This post deals with undirected, weighted graphs and cuts on them. We denote by
the graph equipped with a weight function on its edges. A cut in this graph is a partition of its vertices to
where
. For simplicity, we will only mention one of the parts in the partition, usually
. Note that it doesn’t matter whether we refer to the first part in the partition
, or to the second part
, because both parts define the same cut.
The value of the cut is defined as
A min
-cut for a pair
is a cut defined by
such that
note that it is possible that several cuts will satisfy the definition above, but for our purposes they are equivalent (since they all have the same value).
Before diving into the theorem about cut equivalent trees, we setup the following notation. For a given tree
and any edge
, removing that edge from the tree breaks it down into two connected components, one that contains
, and another one that contains
. Denote the component containing
as
, and then the other component is exactly
. Since the only path connecting
and
was the removed edge, then
is actually the min
-cut in
(the same is true for
since it defines the same cut).
A simple fact about trees is, that for any tree
and vertices
inside it, the min
-cut is given by
where
is the edge with minimum weight along the path that connects
and
. Since any
vertices tree has exactly
edges, there are at most
unique values of min-cuts that the tree can yield.
Cut-Equivalent Trees [Gomory and Hu, 1961]. For any weighted undirected graph
there is a weighted tree on the same set of vertices
such that:
(a) for any , the value of the min -cut in is equal the value of the min -cut in (with respect to their respective weight functions), and
(b) for any edge , Such trees are known as Cut-Equivalent trees (also known as GH-trees).
(a) for any , the value of the min -cut in is equal the value of the min -cut in (with respect to their respective weight functions), and
(b) for any edge , Such trees are known as Cut-Equivalent trees (also known as GH-trees).
The proof is omitted from this post, and we move to discuss a nice implication of that theorem: it puts a limit on the number of different min-cut values that a graph can have. Since there are
different
pairs in a graph there can be potentially
unique min-cut values, however, the theorem says that any value of a min-cut in
is being represented by a (possibly different) min-cut in
, and there are at most
min-cut values in
, then
has at most
unique min-cut values.
3 General Cuts in a Graph
Until now, we talked about minimum
cuts. The theorem above state that for any graph
, there is a cut-equivalent tree
that can tell us much about all the minimum cuts in
. It can tell us all the possible min-cut values that
can have, moreover, for any min-cut value
, there is a very easy way to find a cut in
that have this exact value. All we need to do is to find an edge in the tree that have weight
, suppose that edge is
, and the desired cut in
is given by
.
One interesting question to ask is, what cut-equivalent trees can tell us about “general” cuts? The answer is given in the following theorem.
[Krauthgamer and Pogrow, 2017]. Let
be a weighted undirected graph with
vertices, and let
be a cut-equivalent tree of
. Then for any
We start with the left-hand side. Recall that the value of a cut
is the sum of weights of all the “crossing edges”, meaning, edges which have endpoints in both parts of the partition. Then, combined with the second property of the tree, and the fact that
for any edge
, we get
so it is suffice to show that any crossing edge in the sum of the original graph
, contributes also to a sum of
for some tree-edge
such that
. So fix some crossing edge
(
) from the original graph, and consider the unique path connecting
and
over the tree. Since we starting the path with a vertex from
and ending with a vertex in
, there must be an edge
along the path such that
and
. That edge
separates
from
in the tree, so
and
. Since
then it contributes to
, which is what we wanted to prove.
We proceed to show the second inequality. For each in the sum of , we know that since the weight of the tree-edge is equal to the min -cut in , thus in particular smaller or equal to the value of the cut (which also separates from but might not be of minimum weight). The inequality follows by summing over all the crossing edges in over , which is at most edges.
We proceed to show the second inequality. For each in the sum of , we know that since the weight of the tree-edge is equal to the min -cut in , thus in particular smaller or equal to the value of the cut (which also separates from but might not be of minimum weight). The inequality follows by summing over all the crossing edges in over , which is at most edges.
4 The Inequalities are Tight
We conclude this post with examples for cases in which one of the inequalities became an equality.
For the first inequality, take any graph
and a corresponding cut equivalent tree
. Fix an arbitrary tree-edge
. The cut
is the min
-cut in
and by the first property of the tree
.
For the second inequality, consider the complete graph on
vertices with all its edges weighted
. Its cut-equivalent tree must be a star in which every edge weighed
. See example of an eight vertices star in the figure below (taken from Wikipedia).
Suppose the vertex in the center of the star is
. The cut
has weight of
over
, however, it has weight
in the star
which is exactly
.