Algorithm for independent vertex cover

5
votes

Question from Skiena book on Algorithm:

A vertex cover of a graph G = (V,E) is a subset of vertices V ∈ V such that every edge in E contains at least one vertex from V . An independent set of graph G = (V,E) is a subset of 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 of G. Give an efficient algorithm for testing whether G contains an independent vertex cover. What classical graph problem does this reduce to?

Does anyone know the answer to this question ?

Thanks.

UPDATE

(Need suggestions on this thought)

So far I think this is related to checking whether the graph can be colored using 2 colors, i.e. whether it is bipartite ? If a BFS variant is used to color a graph ,lets say, white and black, then vertices with one of those colors, say white, also forms a vertex cover in some cases.

2
algorithmgraph

2 Answers

4
votes

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.

0
votes

*Independent vertex cover = bipartite graph + minimum vertex cover?*On the same problem