algorithm - NP完全性の証明

Question

グラフの任意の 2 つの頂点間の m 個の最短経路が与えられます。和集合がすべてのエッジをカバーするように k 個の最短パスを選択できるかどうかを判断します。

削減はセットカバーからでなければならないと確信していますが、それをこの問題に削減する方法がわかりません。それを手伝ってください

Answer 1

更新は、セット カバーも NP 完全であることを認識していませんでした。オリジナルを正確なセット カバーに合わせるために何もする必要はないので、私が作成した wlog の仮定は必要ありません。しかし、自分の証明の基本的な考え方が間違っていることにも気付きました。それは、現在の問題が別の問題の特殊なケースであることを示しているため、難しくはなく、簡単になります。完全で正しい答えは、mjqxxxxによるhttps://math.stackexchange.com/q/2047262にあります。

1 つの頂点が複数のパスに属していないと仮定してみましょう (つまり、パスは頂点の個別のセットに対応します)。

次に、この問題は正確なカバーの問題 (NP 完全)であり、1 つだけではなくすべての正確なカバーを見つけるように拡張されています (そして、それらの 1 つに正確なk要素があるかどうかを確認します。このチェックは、一般的には少しトリッキーです) ）。https://en.wikipedia.org/wiki/Exact_cover https://en.wikipedia.org/wiki/Set_cover_problem

セットXにはグラフのすべての頂点がS含まれ、コレクションには指定されたパスのセットに対応する頂点のセットが含まれます。