Iはグラフの問題として考えているグラフ

Question

のスパニングツリーに最大比分カットを見つける、この問題の一部が記載されているようである：我々は、グラフG =（V、E）を有する

、及びグラフを各ノード（U、U '）を有する2つのサブグラフに分割するG（E上）の各最小カットについて、そのスパニングツリーT =（V、F）（FはEのサブセットである）接続する）我々はFで、このカットの大きさを確認し、それらの名前のサイズG（U、U「）とT（U、U」）、私が知りたい：

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

私はこれがあると思いますNP - ハード、しかし私はそれを証明することはできません。何か、それが0 <比明らかである、我々はGと同じ程度とTで頂点を持っている場合には、比率が1であるが、ここでは明らかである< = 1

Uは、U「= nullを、UユニオンU」が交差します= Vであり、UおよびU 'のいずれも空ではない。

Answer 1

これは、一般的な単位要求を持つ単位重さツリーでの非均一な高密度カット問題です。 2011年の論文では、Bonsma et al.州によってオープンな問題として、非均一の複雑さがありますsparsest一般的な単位の要求との境界線トレッドの単位重量グラフをカットするので、あなたの問題はあまりにも希薄で最も密度の高いカットは非常に密接です（基本的には一様な要求に対して同じ）。