問題タブ [independent-set]

ご存じのように、最大​​独立集合を見つけることは NP です。特定のグラフに少なくとも k 個の頂点の独立したセットがあるかどうかを調べるアルゴリズムはありますか? 見つけたくないことに注意してください。そのようなものが存在するかどうかを知りたいだけです。

すべての可能な独立集合の中から最大値を見つける力ずくの方法以外に、2部グラフで最大の独立頂点集合を見つけるためのアルゴリズムは存在しないと思います。

考えられるすべての頂点セットを見つけるための擬似コードについて疑問に思っています。

4つの青い頂点と4つの赤い頂点を持つ2部グラフが与えられたとしましょう。現在私は

最初のステップの後、すべての可能性をステップスルーするのではなく、一致しない次の色の頂点をすべて選択するため、この方法ではすべての可能な独立集合の組み合わせが得られるわけではないことを理解しています。

たとえば、一致するグラフがあるとします

このアルゴリズムを改善して、すべての可能性をより適切に検索する方法はありますか？|2部グラフの最大セット| =|赤| +|青| -|最大マッチング|。

問題は、特定の青に対して最初にすべての可能な赤を選択することによって、それらの赤が他のすべての可能な青に接続する場合、私のセットにはすべて1つの青と残りの赤しか含まれない可能性があるために発生します。

ツリー内の最大独立セットを見つけるアルゴリズムが必要です。すべてのリーフ ノードから開始し、これらのリーフ ノードの直接の親ノードを削除してから、削除した親ノードの親ノードを選択し、ルートに到達するまでこの手順を再帰的に繰り返すことを考えています。これはO（n）時間で行われますか？どんな返信でも大歓迎です。ありがとう。

そして、ツリー内の最大支配セットを見つけるためのアルゴリズムを教えてください。

無向グラフのすべての独立した集合を生成するアルゴリズムが必要です。

例えば：

'Bron-Kerbosch'アルゴリズムを使用しようとしましたが、結果の解釈方法がわかりません。

入力：

A = [1 2; 1 5; 2 3; 2 5; 3 4; 4 5; 4 6]

望ましい出力:

B = [1 3 6; 1 4; 2 4; 2 6; 3 5 6]

結果をどう解釈するか？

ありがとうございました！

s-clique を s-independent セットに変換することに関するアルゴリズム クラスの宿題の質問があります。以下はコードで、一番下の関数independent_set_decision(H,s)は私が完了する必要があるものです。私は困惑しています。

連結リスト (または有向非巡回グラフ) に似たグラフがあるとします。独立セットは、セット内の他のノードとエッジを共有しないノードで構成されます。各ノードが重み付けされている場合、ノードの独立したセットの最大可能値をどのように計算できますか? 動的プログラミングを使用する必要があることは理解しているので、少し手がかりがありますが、誰かがどのようにアプローチするかを説明してくれることを願っています. ありがとうございました！

男性と女性のリストがあるとしましょう。各男性 (x) は各女性を評価し、各女性 (y) は各男性を 0 ～ 9 のスケールで評価します。

例えば

x1: {y1: 0、y2: 5、y3: 9}

x2: {y1: 1, y2: 0, y3: 9}

x3: {y1: 5, y2: 5, y3: 8}

y1: {x1: 3, x2: 3, x3: 5}

y2: {x1: 8, x2: 2, x3: 2}

y3: {x1: 9, x2: 5, x3: 9}

合計評価を最大化するために、すべての x と y をペアにするアルゴリズムを探しています。

この場合、最適なペアリングは x2:y3 = 9+9 = 18、x1:y2 = 5+8 = 13、x3:y1 = 5+9 = 14 です。合計評価は 45 です。少なくとも私はそう思います。目によるものです。

これは最大独立集合問題の単純化されたバージョンであり、NP 困難な最適化問題ではないと思います。

n 個の 2D 点を含む単位正方形を考えます。2 つの点 p と q は、それらの間のユークリッド距離が 1 より大きい場合、正方形内で独立していると言えます。単位正方形には、最大 3 つの相互に独立した点を含めることができます。O（n log n）の指定された単位正方形で、相互に独立した3つの点を見つけたいと思います。出来ますか？私を助けてください。

この問題は、Quadtree、kd-tree などの空間データ構造を使用せずに O(n^2) で解決できますか?

まず、これは私の宿題だと言いたい。ただし、私の問題を解決するために、必要な文献を使用できます。

問題はその名前から明らかだと思いますが、次のように説明します。サイズK.」

からおよび から3-SATへの多項式簡約について知っています。( http://mlnotes.com/2013/04/29/npc.html ) ただし、これら 2 つの削減を組み合わせることができないため、これには問題があります。からへの削減も試みましたが、あまり成功しませんでした。CLIQUE3-SATINDEPENDENT-SETCLIQUECLIQUE-OR-INDEPENDENT-SET

だから私は本当にヒントをいただければ幸いです！

前もって感謝します。