algorithm - 在图的生成树中找到最大比率最小切割

Question

我正在考虑一个图形问题，这个问题的一部分如下所述:

我们有一个图 G=(V,E)，它的生成树 T=(V,F)(F 是 E 的子集)，对于 G 中的每个最小割(在 E 上)，它将图划分为两个带有节点 (U,U') 的子图(不需要连接每个子图)我们检查 F 中这个切割的大小，将它们的大小命名为 G(U,U') 和 T(U,U')，我想找到:

ratio = max{T(U,U')/G(U,U')} for all possible U,U'

我认为这是 NP-Hard，但我无法证明。这里有一点很明显，那就是如果我们在 T 中有一个与 G 具有相同度数的顶点，则比率为 1，而且很明显 0 < ratio <= 1。

U 相交 U' = null，U 并集 U' = V，并且 U 和 U' 都不为空。

Answer 1

这是具有一般单位需求的单位权重树中的非均匀最密集切割问题。 Bonsma et al. 2011 年的一篇论文将非均匀 sparsest 的复杂性声明为一个开放的问题，在具有一般单位需求的有界树宽的单位权重图中进行切割，所以我怀疑你的问题也是开放的 - 最稀疏和最密集的切割非常接近相关(统一需求基本相同)。