# Scheduling problem on bipartite graph

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 needs to be scheduled.

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? • Welcome to CS.SE! What are your thoughts? What have you tried? We don't want to just do your exercise for you: we want you to gain understanding, but as you haven't given us much to work with, it's not clear how to help you. – D.W. Dec 10 '15 at 6:08
• Hi, thanks for your comment. I don't know much about graph theory. I was hoping that the problem I described here may be some form of a known problem, and people who are more knowledgeable on this topic can provide some reference. – user43498 Dec 10 '15 at 16:52

## 1 Answer

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.

• Sorry for the confusion in notation, u and v are vertices one each side. – user43498 Dec 10 '15 at 16:45
• I guess the solution I have given would still hold, right ? If it doesn't, tell me exactly why because I still don't completely understand your question – LockStock Dec 10 '15 at 18:53
• How do you know that your proposed algorithm computes the optimal solution? This needs proof. I suspect one can find examples where it doesn't. – D.W. Dec 10 '15 at 19:17
• @D.W. you're right. Will get back with a better one. – LockStock Dec 10 '15 at 19:24