問題タブ [vertex-cover]

以下は、最大二部マッチング問題です: http://www.spoj.com/problems/QUEST4/ フォーラムを通じて、この問題を最小頂点カバー問題に変換できることを知りました。二部マッチング。しかし、問題がどのようにして最小頂点カバーに変換されたのかわかりません。これを理解するのを手伝ってください。

私の研究では、次のような頂点カバー問題の変形に直面しています。

グラフ G、頂点 v、および数値 k が与えられた場合、G が v を含むサイズ k の頂点カバーを持っているかどうかを判断します。

私は文献全体を検索しましたが、同様の問題を見つけることができませんでした。この問題の複雑さに興味があります ( $P^NP[long]$ で完全であることを証明しました)。

問題は、そのような頂点被覆問題の変種を見たことがありますか? この問題をどう呼びますか?

頂点カバー問題のカーネル化アルゴリズムの最適化アルゴリズムを実装しています: 理論と実験 (PDF) 。

章 2.3: Kernelization by linear programmingで少し行き詰まっています。

この手法 (ILP の定式化) の考え方は、次の制約を満たすために、入力グラフのX_u \in \left\{ 0,1 \right\}各頂点u( としても示される) に重みを割り当てることです。vG=\left\( V,E \right\)

• 重みの合計を最小化する\Sigma_uX_u
• グラフのエッジで接続されている場合はX_u + X_v \geq 1いつでも満足します。\left\{ u,v \right \}

したがって、出力としてX_v、1 の頂点と残りX_vの 0を持つ頂点のセットが得X_u \in \left \{ 0,1 \right \}られX_u \geq 0ます。( S. Khuller (PDF)は、この場合それを指摘していX_u \in \left \{ 0,0.5,1 \right \}ます)。その緩和により、重みが 1、0.5、および 0 の頂点の 3 つのグループができます。

私の問題は、重みの割り当てにどのようにアプローチするかがよくわからないことです。

私が理解できたことから、重みの合計を最小限に抑えるには、(エッジごとに) 最初に次数が最も高い頂点に焦点を合わせ、それらの重みが既にゼロより大きい場合は、頂点に値を追加するのが最善です解析されたエッジの 2 番目の端。

X_v \in \left \{ 0,1 \right \}これにより、(正確に?)基本的な定式化の各頂点が実際にある状況につながります。整数制約を緩和しようと考えていると、 に変わりますX_v \in \left \{ 0,0.5 \right \}。

私の論理の欠陥は何ですか？

重みが 1 と 0、および 0.5 の頂点を持つには、緩和にどのようにアプローチする必要がありますか?

グラフの頂点カバーを見つけるためのアルゴリズムはたくさんありますが、大きなグラフの頂点カバーを見つけるための並列アプローチとして使用できる最適なアルゴリズムを知りたいので、どれが最適ですか? 私がこの質問をしたので、実際のアプリケーションでのこの問題の重要性は、テロリスト通信 N/w、航空会社通信 N/w、ワイヤレス通信などに似ています。

木の頂点被覆問題は次のとおりです。

入力:非巡回単純無向グラフ G
出力:すべてのエッジ uv について、u ∈ W または v ∈ W となるような頂点 W の集合。W のサイズを最小化したい。

私の貪欲なアルゴリズムは、W = ∅ を初期化し、G が空でない間、次の手順を繰り返すことです。L を G の葉の頂点とする。N(L) を L のある頂点に隣接する頂点の集合とする。W = W ∪ N(L) を更新する。頂点 L ∪ N(L) とそれらの入射エッジを G から削除します。

このアルゴリズムは、これまでに試したすべてのケースで機能します。それが正しいことを証明するにはどうすればよいですか？これが私がこれまでに持っているものです。

最適解である別の集合 S があるとします。矛盾して、S がすべてのエッジをカバーしていないか、S が貪欲なアルゴリズムによって生成されたものと同じセットであることを立証したいと考えています。

私はこの問題に取り組もうとしています...以下は1つのアルゴリズムです..私は理解しました..

入力グラフは、他のすべてのノードとの一致度が最も高い頂点を選択します。このノードに付随するエッジを削除します。選択した頂点とそのエッジをセット X に追加します。X を返します。

X は、頂点カバーに必要な頂点の最小セットを返します。この方法は正しいですか? ありがとう

頂点の重みがその次数であるツリーを扱う既存の質問がありますが、頂点が任意の重みを持つことができる場合に興味があります。

これは宿題ではありませんが、現在読んでいるアルゴリズム設計マニュアルの質問の 1 つです。回答セットは次のように解を与えます

1. DFS を実行し、各ステップで Score[v][include] を更新します。v は頂点で、include は true または false です。
2. v がリーフの場合、Score[v][false] = 0、Score[v][true] = w _vを設定します。ここで、w _vは頂点 v の重みです。
3. DFS 中に、ノード v の最後の子から上に移動するときに、Score[v][include] を更新します。 Score[v][false] = Score[c][true] と Score の children(v) の c の合計[v][true] = w _v + min(Score[c][true]; Score[c][false]) の children(v) の c の合計
4. スコアをバックトラックして実際のカバーを抽出します。

ただし、実際にそれを機能するものに変換することはできません。（コメントへの回答：これまでに試したことは、「実際のカバーを抽出する」部分が透明ではないステップ4まで、重みを使用していくつかの小さなグラフを紙に描き、アルゴリズムを紙に実行することです。）

Aそれに応じて、アリの答え：だから、等によって与えられた頂点とその後のかっこ内の重みを持つこのグラフがあるとします：

A(9)---B(3)---C(2) \ \ E(1) D(4)

正解は明らかに{B,E}です。

このアルゴリズムを使用して、次のように値を設定します。

• score[D][false] = 0;score[D][true] = 4
• score[C][false] = 0;score[C][true] = 2
• score[B][false] = 6;score[B][true] = 3
• score[E][false] = 0;score[E][true] = 1
• score[A][false] = 4;score[A][true] = 12

わかりました、それで、私の質問は基本的に、次は何ですか? 単純なことを実行し、scoreベクトルを反復処理して、ローカルで最も安いものを決定することは機能しません。あなただけを含めることになりBます。親に基づいて決定し、交互にすることも機能しません。の重みが の場合を考えてみましょEう1000。正解は{A,B}で、隣接しています。混乱させるべきではないかもしれませんが、率直に言って、私は混乱しています。

クラスのクイズで、頂点カバーの非決定的アルゴリズムを作成する問題がありました。インストラクターと解決策について話し合ったところ、レベルの不確定性が高すぎてはならないと言われました。それは賢明に良いはずです。
非決定論的コンピューターにどのような質問をすればよいのか混乱しています。

50,000 個の頂点を持つ「ほぼ」ツリーの頂点カバーを取得しようとしています。グラフは、「ほぼ」ツリーにするためにランダムなエッジが追加されたツリーとして生成されます。

2 つの頂点を結合し、それらをカバーに追加してグラフから削除し、別の頂点のセットに移動する近似方法を使用しました。その後、頂点カバー内に隣接するすべての頂点を削除して、頂点の数を減らそうとしました。

私の質問は、頂点カバーをさらに小さくするにはどうすればよいですか? 私はできるだけ低くしようとしています。