私の研究では、次のような頂点カバー問題の変形に直面しています。
グラフ G、頂点 v、および数値 k が与えられた場合、G が v を含むサイズ k の頂点カバーを持っているかどうかを判断します。
私は文献全体を検索しましたが、同様の問題を見つけることができませんでした。この問題の複雑さに興味があります ( $P^NP[long]$ で完全であることを証明しました)。
問題は、そのような頂点被覆問題の変種を見たことがありますか? この問題をどう呼びますか?
私の研究では、次のような頂点カバー問題の変形に直面しています。
グラフ G、頂点 v、および数値 k が与えられた場合、G が v を含むサイズ k の頂点カバーを持っているかどうかを判断します。
私は文献全体を検索しましたが、同様の問題を見つけることができませんでした。この問題の複雑さに興味があります ( $P^NP[long]$ で完全であることを証明しました)。
問題は、そのような頂点被覆問題の変種を見たことがありますか? この問題をどう呼びますか?