Graph algorithm for dividing students into two groups

Question

I'm struggling to create an efficient algorithm that can determine whether a group of students can be divided into two groups.

Note that there are some provided constraints of the type that for (X,Y) student X must be with student Y and some constraints of the type that for (A,B) student A cannot be with student B. Not every student has a constraint on him, and some students have multiple constraints.

I've considered a graph where each student is a node and then two nodes are connected by an edge if the students could be in the same group (e.g. they either have the constraint that they must be together and/or don't have the constraint that they can't be together). But I'm not sure what algorithm I could apply to solve (or proven, given the set of constraints this is impossible), once I have constructed this graph representation.

Any advice is appreciated? Thank you!

Answer 1

You could use below steps and then use Bipartite Graph algorithm.

1. Consider a graph where each student is a node and then two nodes are connected by an edge if the students could not be in the same group.

2. if student A and B must be in same group then connect B to every node that A is connected and connect A to every node that B is connected too.

now you have a graph that you want to check if vertices can be divided into two disjoint sets and there is no edge between two nodes in the same set. this is Bipartite Graph and you can find the algorithms about how to solve this.

Edit with PeterdeRivaz comment

this answer is better as peter said you could change my step to this :

1. Consider a graph where each student is a node and then two nodes are connected by an edge if the students could not be in the same group.

2. if student A and B must be in same group then connect A and B to an imaginary student.

Answer 2

Graph A is a graph for students that should be together, Graph B is a graph for students that cannot be together.

For every two nodes X,Y in A where there is a path from X to Y, if there exists and Edge between X and Y in B, then this problem cannot be solved. Otherwise, it can be solved.

Solving this would be iterative for every set of connected nodes in A, where in every iteration you choose a set at random and try to move it to one of the two groups, checking for the constraint for every node of the set to make sure that you are satisfying the constraints with other nodes in the group. If the constraints could not be satisfied for one node in the set, then add the set to the other group.

You should stop when every set is in one of the two groups with no conflicts.