2

100 万の頂点を持つ最大次数 4 の単純なグラフが与えられます。

最大独立サブセットを見つけたいとします。

一般的にはNPハードです。

次数が最大4であるという事実は、それを計算するための効率的なソリューションを提供しますか?

4

2 に答える 2

3

そのウィキペディアのページをさらに読んで、私は主題についてこれを見つけました：

たとえば、スパース グラフ (エッジの数が多くてもサブグラフの頂点数の定数倍であるグラフ) の場合、最大クリークはサイズに制限があり、線形時間で正確に検出される可能性があります。[6]ただし、同じクラスのグラフ、またはより制限されたクラスの有界次数グラフの場合でも、最大の独立集合を見つけることは MAXSNP 完全であり、一定の c (次数に応じて) に対して NP であることを意味します。 - 最適値の c 倍以内に収まる近似解を見つけるのは困難です。[7]

あなたのケースは境界度のケースであるため、このスニペットから判断すると、より制限的なバージョンはまだ NP 困難です。

于 2012-08-02T17:09:19.633 に答える
1

非常に単純な貪欲な 1/5 近似があります。任意の頂点を取り、それを独立集合に追加し、グラフから隣接を削除します。頂点がなくなるまで続けます。このトリックのもう少し一般的なバージョンは、Turan の定理です。

于 2012-08-06T17:16:15.557 に答える