Scheduling problem on bipartite graph

Question

Consider a bipartite graph $G=(U, V, E)$. Each $v \in V$ represents a soccer team, and each $u \in U$ represents a mini-tournament which needs to be scheduled. Tournament $u$ is adjacent to team $v$ if $v$ plays in that tournament $u$. Each tournament uses a full day.

If $u_i$ and $u_j$ share no common neighbor, these two tournament can be scheduled on the same day. Similarly, one can schedule multiple tournaments in one day if there is no such conflict.

Is there a way to compute the minimum number of days required to complete all the tournaments and the corresponding scheduling?

Answer 1

While this seems like homework, since it was asked 8 years ago it is probably past the point that the question asker can benefit from this for that course.

Build a graph $G_2 = (U, E_2)$ of where the vertices of $G_2$ are only the $u$-vertices from your original graph. And join an edge between any two tournaments $u_i, u_j$ if they are in conflict (i.e. if there exists some $v_k$ adjacent to each of $u_i$ and $u_j$ in your original graph).

This is normally called the conflict graph of a set of objects - in this case, your set of objects are tournaments, some of which are in conflict with others.

A minimum colouring of this $G_2$ graph will provide the minimum number of tournament days to complete all of them. Each colour corresponds to a day, so two tournaments with the same colour in an optimal colouring would be an example of two tournaments that play on the same day.

Extra Aside: This can be used to show your problem is NP-hard. Consider any graph colouring instance - then you can make all the vertices of this instance a set of $U$-nodes, and for every edge in the graph colouring instance, create a $v$-node adjacent to these two edge endpoints. This constructs a rather simple (but somewhat larger) instance of your tournament problem. The problem size would still be O(n+m) and so this is a polytime construction.

Answer 2

So here, it looks as though $u \in U$ is a vertex representing the team and $v \in V$ is an edge between the vertices representing the matches possible.

If we can generate a Bipartite Graph, the edges ${ v_i, ...v_j}$ going across are all non-conflicting matches. Those edges for this matching ( $M_1$) can be held on that day. Next, we remove ${ v_i, ...v_j}$ and check to see if we can get more Bipartite Graphs. The edges going across are similarly the non-conflicting matches.

Not sure if this is what you asked for.