algorithm - 最小頂点カバー

Question

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

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

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

Answer 1

これは、少数のリンクのみが追加された場合、またはノード間の距離があまり変化しない場合に扱いやすい正確な答えの試みです。

最小スパニング ツリーを見つけ、エッジを「ツリー エッジ」と「追加エッジ」に分割します。ここで、ツリー エッジは最小スパニング ツリーを形成し、追加エッジはこのために選択されませんでした。構築中に実際に追加されたエッジではないかもしれませんが、それは問題ではありません。N ノード上のすべてのツリーには N-1 個のエッジがあるため、同じエッジでなくても、作成時に使用されたのと同じ数のエッジが追加されます。

ここで、本の後ろにある答えを見て、追加された各エッジから 1 つの頂点について、その頂点が最適な頂点カバーの一部であったかどうかを確認できると仮定します。そうであった場合は、その頂点とそのリンクを問題から削除できます。そうでない場合は、問題からその頂点とそのリンクを削除できるように、他の頂点が存在する必要があります。

1 本のツリーまたは複数の切断されたツリーの最小の頂点カバーを見つける必要があります。これを行う方法はわかっています。もう少し手を振る方法については、他の回答を参照してください。

答えを求めて本の裏をのぞくことができず、追加されたエッジが k 個ある場合は、本の裏にあった可能性のある 2^k のすべての答えを試して、最良のものを見つけてください。運が良ければ、追加されたリンク A は、追加されたリンク B とは異なるサブツリーにあります。その場合、追加されたリンク A (または B) の 2 つの可能性に必要な 2 つの計算を、関連するサブツリーの動的計画法の計算に限定できます。仕事を 4 倍にするのではなく、2 倍にしただけです。一般に、追加された k 個のエッジが互いに干渉しない k 個の異なるサブツリーにある場合、コストは 2^k ではなく 2 倍になります。

Answer 2

最小頂点カバーは NP 完全アルゴリズムです。つまり、100 個の頂点 (50k は言うまでもありません) のようなものでも妥当な時間で解決することはできません。

ツリーの場合、DFS に基づく多項式時間貪欲アルゴリズムがありますが、「ランダムなエッジが追加された」という事実はすべてを台無しにし、このアルゴリズムを役に立たなくします。

ウィキペディアには 近似アルゴリズム に関する記事があり、係数 2 に達すると主張し、より良いアルゴリズムは知られていないと主張しているため、アルゴリズムが見つからない可能性が高くなります。