# No nice generalization of Gomory-Hu tree

Gomory-Hu tree of a graph $$G$$ is a weighted graph $$H$$ on the same set of vertices. It has the two nice properties.

1. It is a tree.
2. For every $$s,t$$, there exist a min-$$st$$-cut in $$H$$ that is also a min-$$st$$-cut in $$G$$.

We could ask for a generalization. Given a graph $$G$$, can we find some nice graph $$H$$ such that

For every $$S,T$$ such that $$1\leq |S|,|T|\leq k$$ and $$S\cap T=\emptyset$$, there is a min-$$ST$$-cut in $$H$$ that is a min-$$ST$$-cut in $$G$$.

We recover Gomory-Hu tree when $$k=1$$. There were some consideration of a problem similar to this [1].

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 $$k=2$$, there are graphs where $$H$$ is almost the complete graph.

Let $$G$$ be the complete graph on $$n$$ vertices, and each edge has capacity $$1$$. Let $$f(S)$$ be the sum of the capacity of edges going across $$S$$. There is a unique $$ST$$-min cut for every $$|T|=1$$ and $$|S|=2$$. Hence this shows that $$f(\{v\}) = n-1$$ for every $$v\in V$$. If $$|S|=|T|=2$$, there are exactly two min $$ST$$-cuts, either $$S$$ or $$T$$ in $$G$$. Assume that $$T$$ is not a min $$ST$$-cut in $$H$$, then $$S$$ has to be the min $$ST$$-cut in $$H$$. Therefore for all $$\{s_1,s_2\}$$ such that $$s_1,s_2\not \in T$$, we have $$f(\{s_1,s_2\})=2n-4$$. Because $$f(\{s_1\})=f(\{s_2\})=n-1$$, the edge between $$s_1$$ and $$s_2$$ has capacity $$1$$. The complete graph on $$V\setminus T$$ has to be a subgraph of $$H$$.

# Reference

[1] R. Chitnis, L. Kamma, R. Krauthgamer, Tight Bounds for Gomory-Hu-like Cut Counting, ArXiv E-Prints. (2015).

Posted by Chao Xu on 2016-02-01.
Tags: .