Issue with Gomory Hu Tree

Hi, I’m using the gomory_hu_tree function, but I’ve run into an issue. I’m wondering if the function is actually returning an equivalent flow tree and not the Gomory Hu tree (as discussed in Gusfield 1990)? Although I might have misunderstood something.

I’ve created a MWE (in python igraph), using G a K4 graph. It gives a Gomory Hu tree that is a path (0–1–2–3), with all edges weight 3.

In a Gomory Hu Tree, for given vertices x,y, the smallest weight edge e on the x-y path in T induces a cut represented by the components of T-e that is a minimum x-y cut in G.

However if we take x,y to be 1,2 in the MWE, the cut induced by the only edge e on the 1-2 path induces a cut ({0,1}, {2,3}) in G, which is weight 4, and not a minimum 1-2 cut in G.

So it seems like the tree returned by the function is a correct equivalent flow tree, but not a Gomory Hu tree.

The Gomory Hu tree of K4 should be a star, with all edges weight 3.

MWE

import igraph as ig
G= ig.Graph.Full(n=4)
T = G.gomory_hu_tree(flow="label")
visual_style = {}
visual_style["vertex_color"] = "white"
visual_style["vertex_label"] = range(4)
ig.plot(T, **visual_style)

My apologies in advance if I’ve misunderstood something.

Thanks
Michal

As you say, in Gusfield 1990, equivalent flow tree is used for a tree which is suitable for determining the size of the minimum cut, but not the actual cut. He refers to the specific equivalent flow tree which also provides the cut (not just its value) as GH cut tree. As you observe, igraph appears to compute the former.

@tamas, as I recall, you implemented this function originally. Can you recall if the intention was to compute only the equivalent flow tree? A very quick skim of the Gusfield paper (also referenced in the igraph docs) suggests to me that there are two algorithms discussed: one for an equivalent flow tree, and another for the GH cut tree.

Questions to consider:

  • Is the documentation correct? Yes, it is, it describes a tree that is suitable for determining the cut value (not the cut itself).
  • Is the terminology used by igraph standard? Personally I cannot say much on this, as I have not looked at GH trees in detail so far. While the terminology does not agree with Gusfield 1990, it does agree with Wikipedia, which uses “GH tree” for the same thing that Gusfield describes as “equivalent flow tree”. Input on this is welcome, @salterduke, preferably with references.
  • Should igraph have a function which computes a tree that is suitable for determining the cut itself (not just its value)? Of course, it would be nice, but our time is constrained. You are welcome to open a feature request on GitHub, @salterduke, if you need this, but we cannot make any promises about when it might get implemented. Feature requests are still useful as we can gauge what most users need. You are also welcome to contribute an implementation (programmed in C), if you are feeling up to the task. We are happy to provide guidance for navigating igraph’s internals.

I’m sorry, I was wrong here. Wikipedia does in fact talk about the trees which represent the entire cut, not just its value. Some googling suggests that this is the usual thing meant by the “Gomory Hu tree”. Thus we might in fact have a problem with the terminology used by igraph, or even a bug in the implementation (@tamas?)

You convinced me that something is wrong. I opened a bug report. Thanks for bringing up this issue!

Unfortunately it wasn’t me, it was Gábor; I think 99% of the flow- and cut-related functions were his work originally. I’m happy to dig into this and figure out whether the terminology is right or not but first I need to understand what a Gomory-Hu tree is :slight_smile:

@tamas Please see the issue I opened for more details. The solution seems to be within easy reach (and yes, now I’m convinced that this is a bug in the implementation).

1 Like

This is now fixed in fix: fix a bug in the Gomory-Hu tree calculation; it used to calculat… · igraph/igraph@398fb42 · GitHub in the C core.

1 Like