Graph Complement, Two-coloring.
Given a graph G = (V, E), determine, whether its vertices can be partitioned into two sets V1 and V2, such that both V1 and V2 form a clique in G.
Such a partition is possible, iff the complement of graph G is a bipartite graph.
Suppose for a given graph G = (V, E), we can partition the vertices into two sets V1 and V2, such that both V1 and V2 form a clique in G.
Let us say that H = (V, E’) is the complement graph of G, which has the same vertex set as that of G, however an edge (u, v) exists in H iff the edge (u, v) does not exist in G, and vice versa.
Since V1 forms a clique in G (i.e., all vertices of V1 are connected with each other via an edge), it must form an independent set in H (i.e., no two vertices of V1 are connected by an edge in H). The same holds for the set V2.
In other words, the vertex set V can be partitioned into two sets V1 and V2, such that both V1 and V2 form independent set in H. In other words, all edges of H are of the form (u, v), where u belong to the set V1, and v belong to the set V2. In other words, H is a bipartite graph.
Hence, we only need to check whether the graph H is a bipartite graph. This can be done in the linear time (in the number of edges and vertices) using a depth first traversal of the graph as shown here.
O (N2), where N is the number of vertices in the graph.
Note that the bipartiteness can be checked in linear time, however the complement of input graph may have quadratic number of edges. Hence, the complexity of this method is O (N2).
AUTHOR’S AND TESTER’S SOLUTIONS:
Tester’s solution will be uploaded soon.