查找在跨越的曲線圖

Question

我正在考慮中的圖表的一個問題的樹min切削最大比率，該問題的一個部分是具有描述：

我們有一個圖形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 <比< = 1

ü相交U「=零，U工會U」 = V，並且U和U'都不是空的。

Answer 1

這是具有一般單位需求的單位重量樹中的非均勻最密切割問題。 2011年的一篇文章Bonsma et al.說明了一個未解決的問題，非均勻的複雜性最稀疏在有限的樹寬與一般單位需求的單位權重圖中減少，所以我懷疑你的問題是開放的 - 最稀疏和最密切的切割非常緊密相關（統一要求基本相同）。