# 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 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?

• 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, 2015 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. Dec 10, 2015 at 16:52

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.

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. Dec 10, 2015 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 Dec 10, 2015 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, 2015 at 19:17
• @D.W. you're right. Will get back with a better one. Dec 10, 2015 at 19:24