Skiena关于算法的书的问题：
图 G = (V,E) 的顶点覆盖是顶点 V ∈ V 的子集，使得 E 中的每条边都包含至少一个来自 V 的顶点。图 G = (V,E) 的独立集是顶点 V ∈ V 的子集，使得 E 中的任何边都包含 V 中的两个顶点
独立顶点覆盖是顶点的子集，既是独立集又是G的顶点覆盖。给出一个有效的算法来测试G是否包含独立顶点覆盖。这会减少到什么经典的图问题？
有谁知道这个问题的答案？
谢谢。
更新
（需要关于这个想法的建议）
到目前为止，我认为这与检查图形是否可以使用 2 种颜色着色有关，即它是否是二分的？如果使用 BFS 变体为图形着色，比如白色和黑色，那么在某些情况下，具有其中一种颜色的顶点（比如白色）也会形成顶点覆盖。
Your thought is correct. It is the problem of checking if a given graph is bipartite.
Bipartite graphs do not have cycles of odd length, so if you use a BFS to color a graph, the vertices of the same colour will be independent sets.
From Wikipedia:
If a bipartite graph is connected, its bipartition can be defined by the parity of the distances from any arbitrarily chosen vertex v: one subset consists of the vertices at even distance to v and the other subset consists of the vertices at odd distance to v.
Thus, one may efficiently test whether a graph is bipartite by using this parity technique to assign vertices to the two subsets U and V, separately within each connected component of the graph, and then examine each edge to verify that it has endpoints assigned to different subsets.
The interesting fact is that independent set is Np-complete and vertex cover too, but verifing if a graph is bipartite is plynomial.
In future, for questions like this, also https://cs.stackexchange.com/ is a great place to ask.
*独立顶点覆盖 = 二分图 + 最小顶点覆盖？*同样的问题