集合 A = {a 1 ,a 2 ,...,a n }が与えられます
B 1、B 2、...、B mという名前の A のサブセットが与えられます。H という名前の A のサブセットが、指定されたすべての B と交差する場合、H を「カバー サブセット」と呼びます。与えられた A と B に対してサイズ K (H のカーディナリティは K) の「カバーするサブセット」はありますか? この問題が NP 完全であることを証明してください。
いくつかの既知の問題を「サブセットをカバーする」問題に減らす必要があります。
update これをヒッティングセットといいます。ウィキペディアの記事で同じ答えを読むことができます。
この問題は、ある意味で、セット カバーの問題と二重になっています。
一部の用語を変更します。{B1, B2, ...}be要素とbe集合{a1, a2, ...}とする。セットが元の問題に含まれている場合、 「セット」には新しい問題aiの「要素」が含まれています。 BjBjai
aiここで、すべての「要素」をカバーする「セット」の最小数を選択する必要がありますBj。上のリンクに示されているように、その問題は NP 完全です。
変換を明確にするために、set/element と contains/contained を置き換えるだけで、1 つの問題定義を別の問題定義から生成できます。以下を比較
すべてのセットBjには選択された要素が含まれていますai
すべての「要素」Bjは選択された「セット」に含まれていますai