No nice generalization of Gomory-Hu tree
Gomory-Hu tree of a graph is a weighted graph on the same set of vertices. It has the two nice properties.
- It is a tree.
- For every , there exist a min--cut in that is also a min--cut in .
We could ask for a generalization. Given a graph , can we find some nice graph such that
For every such that and , there is a min--cut in that is a min--cut in .
We recover Gomory-Hu tree when . There were some consideration of a problem similar to this .
There are various useful definition of nice , for example sparse or bounded treewidth. Likely none of them would apply, because we can show that for , there are graphs where is almost the complete graph.
Let be the complete graph on vertices, and each edge has capacity . Let be the sum of the capacity of edges going across . There is a unique -min cut for every and . Hence this shows that for every . If , there are exactly two min -cuts, either or in . Assume that is not a min -cut in , then has to be the min -cut in . Therefore for all such that , we have . Because , the edge between and has capacity . The complete graph on has to be a subgraph of .
 R. Chitnis, L. Kamma, R. Krauthgamer, Tight Bounds for Gomory-Hu-like Cut Counting, ArXiv E-Prints. (2015).