アルゴリズムに関するSkienaの本からの質問：
グラフの頂点被覆G=（V、E）は、頂点V∈Vのサブセットであり、EのすべてのエッジにVからの頂点が少なくとも1つ含まれます。グラフの独立集合G=（V、E）は、頂点V∈Vのサブセットであり、EのどのエッジにもVからの両方の頂点が含まれていません。
独立頂点被覆は、Gの独立集合と頂点被覆の両方である頂点のサブセットです。Gに独立頂点被覆が含まれているかどうかをテストするための効率的なアルゴリズムを提供します。これはどのような古典的なグラフの問題になりますか？
誰かがこの質問への答えを知っていますか？
ありがとう。
アップデート
（この考えについての提案が必要です）
これまでのところ、これはグラフが2色を使用して色付けできるかどうか、つまり2部グラフであるかどうかの確認に関連していると思います。BFSバリアントを使用してグラフに色を付ける場合、たとえば白と黒の場合、これらの色の1つ、たとえば白の頂点も頂点被覆を形成する場合があります。
あなたの考えは正しいです。これは、特定のグラフが2部グラフであるかどうかを確認する問題です。
2部グラフには奇数の長さのサイクルがないため、BFSを使用してグラフに色を付ける場合、同じ色の頂点は独立したセットになります。
ウィキペディアから：
2部グラフが接続されている場合、その2部グラフは、任意に選択された頂点vからの距離のパリティによって定義できます。1つのサブセットはvまでの距離が偶数の頂点で構成され、もう1つのサブセットはvまでの距離が奇数の頂点で構成されます。
したがって、このパリティ手法を使用して、グラフの各連結成分内で2つのサブセットUとVに頂点を個別に割り当てることにより、グラフが2部グラフであるかどうかを効率的にテストし、各エッジを調べて、異なるエンドポイントが割り当てられていることを確認できます。サブセット。
興味深い事実は、独立集合がNp完全で頂点被覆もあるということですが、グラフが2部グラフであるかどうかの検証は多項です。
将来的には、このような質問については、 https：//cs.stackexchange.com/も質問するのに最適な場所です。
*独立した頂点被覆=2部グラフ+最小頂点被覆？*同じ問題について