The Art Gallery Guardian

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\).


[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: .