Divide a graph into two sets

Question

The Question is from Code jam.

Question:
Is there any way to divide the nodes of a graph into two group such that any two nodes which can't remain in the same group should be in different group.
Is there any standard algorithm for this?

How should I tackle this problem when each group should have equal element.

Answer 1

First, the feasibility problem (is there such set/ doesn't exist such set) is 2-coloring problem, where:

G = (V,E)
V = { all nodes } 
E = { (u,v) | u and v are "troubling each other" } 

This problem is solved by checking if the graph is bi-partite, and can be done using BFS.

---

How to tackle the problem when each group should have equal element.

first, let's assume the graph is bi-partite, so there is some solution.

Split the graph into set of connected components: (S1,S2,S3,...,Sk).
Each connected component is actually a subgraph (Si = Li,Ri) - where Li,Ri are the two sides of the bipartite graph (there is only one such splitting in each connected component, if ignoring the order of Li and Ri).

Create a new array:

arr[i] = |Li| - |Ri|   
where |X| is the cardinality of X (number of elements in the set)

Now, solving this problem is same as solving the partition problem, which can be done in pseudo-polynomial time (which is polynomial in the number of nodes).

The solution to partition problem splits each arr[i] to be in A or in B, such that sum{A} is closest as possible to sum{B}. If arr[i] is in A, in your solution, color Li with "1", and Ri with "2". Otherwise - do the opposite.

Solution will be O(k*n+m), where k is number of connected components, n is number of nodes in the graph, and m is number of edges in the graph.

Answer 2

You build a graph from the given nodes (using a hash-table to map names to nodes) and then you use BFS or DFS to traverse the graph and determine if its bipartite (that is, divisibe into two disjoint sets such that a node in one set is only in "trouble" with nodes in the other set, but not with any node in its own set). This is done by assigning a boolean value to each node as its visited by the BFS/DFS and then checking if any of its visited neighbors has the same value, which means the graph is not bipartite (not divisible into two groups).