The Art Gallery Guardian

No nice generalization of Gomory-Hu tree

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

  1. It is a tree.
  2. For every s,ts,t, there exist a min-stst-cut in HH that is also a min-stst-cut in GG.

We could ask for a generalization. Given a graph GG, can we find some nice graph HH such that

For every S,TS,T such that 1S,Tk1\leq |S|,|T|\leq k and ST=S\cap T=\emptyset, there is a min-STST-cut in HH that is a min-STST-cut in GG.

We recover Gomory-Hu tree when k=1k=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=2k=2, there are graphs where HH is almost the complete graph.

Let GG be the complete graph on nn vertices, and each edge has capacity 11. Let f(S)f(S) be the sum of the capacity of edges going across SS. There is a unique STST-min cut for every T=1|T|=1 and S=2|S|=2. Hence this shows that f({v})=n1f(\{v\}) = n-1 for every vVv\in V. If S=T=2|S|=|T|=2, there are exactly two min STST-cuts, either SS or TT in GG. Assume that TT is not a min STST-cut in HH, then SS has to be the min STST-cut in HH. Therefore for all {s1,s2}\{s_1,s_2\} such that s1,s2∉Ts_1,s_2\not \in T, we have f({s1,s2})=2n4f(\{s_1,s_2\})=2n-4. Because f({s1})=f({s2})=n1f(\{s_1\})=f(\{s_2\})=n-1, the edge between s1s_1 and s2s_2 has capacity 11. The complete graph on VTV\setminus T has to be a subgraph of HH.


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

Posted by Chao Xu on .
Tags: Algorithm.