これが質問です。明確で効率的な証拠があるかどうか疑問に思っています:
頂点カバー: 入力無向 G、整数 k > 0。すべてのエッジをカバーする頂点 S のサブセット (|S|<=k) はありますか?
Dominating Set: input undirected G, integer k > 0. すべての頂点を支配する頂点 S のサブセット (|S|<= k) はありますか?
頂点は、そのインシデント エッジをカバーし、隣接するエッジとそれ自体を支配します。
VC を NPC とすると、DS が NPC であることを証明せよ。
非常によく知られたリダクションがあります。
Vertex Cover のインスタンス (G,k) が与えられた場合、Dominating Set (H,k) のインスタンスを作成します。ここで、H の場合は G を使用し、すべての孤立した頂点を削除し、すべてのエッジ (u,v) に追加の頂点 x 接続を追加します。 u と v に。
まず、G の Vertex Cover が H の Dominating Set であることを認識します。これは G の DS (孤立した頂点を削除した後) であり、新しい頂点も支配されます。したがって、G の VC が k より小さい場合、H の DS は k より小さいです。
逆に、H の支配集合である D を考えます。
新しい頂点の 1 つが D にある場合、それを 2 つの隣接する頂点の 1 つに置き換えても、支配セットを取得できることに注意してください。隣接するのは元の 2 つの頂点だけであり、それらも接続されています。x が支配できる可能性のあるものはすべてまた、u または v によって支配されます。
したがって、D には G からの頂点のみが含まれると仮定できます。G のすべてのエッジ (u,v) について、新しい頂点 x は D によって支配されるため、u または v のいずれかが D にあります。しかし、これは、D が の頂点カバーであることを意味します。 G.
G は、H がより小さい k の支配セットを持っている場合に限り、より小さい k の頂点カバーを持ちます。
から取得：
CMSC 651 Advanced Algorithms 、講師 Samir Khuller
2番目の問題はNPではないと思います。次のアルゴリズムを試してみましょう。
1. Get the original Graph
2. Run any algorithm which checks if a graph is connected or not.
3. mark all used edges of step 2
4. if the graph is connected then return the set of marked edges otherwise there is no such a set.
私があなたの問題を正しく理解していれば、それはNP完全ではありません。