Independent Vertex Algorithm

Question

Question from Skien's book on the algorithm:

The covering of the vertices of the graph G = (V, E) is a subset of the vertices V ∈ V such that each edge in E contains at least one vertex from V. An independent collection of the graph G = (V, E) is a subset of the vertices V ∈ V such that no edge in E contains both vertices from V

An independent vertex cover is a subset of vertices that is both an independent set and a vertex cover G. Give an efficient algorithm to check if G contains an independent vertex cover. What problem does the classical graph reduce to?

Does anyone know the answer to this question?

Thanks.

UPDATE

(Need suggestions on this thought)

So far, I think this has to do with checking if the graph can be colored using two colors, i.e. Is he dicotyledonous? If the BFS variant is used to color the graph, say, white and black, then vertices with one of these colors, for example, white, also form in some cases a vertex cover.

Answer 1

Your thought is correct. This is the problem of checking whether a given chart is bipartite .

Two-sided graphs do not have odd-length loops, so if you use BFS for a color plot, vertices of the same color will be independent.

From Wikipedia:

If a bipartite graph is connected, its bipartite distribution can be defined as follows: the parity of the distances from any arbitrarily selected vertex v: one subset consists of vertices at an even distance to v, and the other subset consists of vertices at an odd distance to v.

Thus, you can effectively check whether the graph is bipartite using this parity method to assign vertices to two subsets of U and V, separately in each connected component of the graph, and then check each edge to make sure that it has endpoints assigned to different subsets. .

An interesting fact is that the independent set is an Np-complete and vertex covering, but checking if the graph is bipartite is plynomial.

In the future, for such questions, also https://cs.stackexchange.com/ is a great place to ask.

Answer 2

* Independent vertex coverage = bipartite graph + minimum vertex coverage? * For the same task