Speed dating and graph theory

Suppose you are organising a speed dating event. You are given a graph G = (S,P). The event consists of a number of rounds; in the ith round of the event, you must pick a subset P_i\in P such that no s\in S appears in two elements of P_i, and P_i\cap P_j = \varnothing for all j < i. (That is, no person may be in two dates at the same time, and the same date may not occur in two rounds.) The event lasts for R rounds, finishing when \cup_{1\leq i\leq R} P_i = P. (That is, when all possible dates have occurred). The ‘idle time’ is defined as T = \sum_{1\leq i\leq R} \sum_{s\in S} 1(s \not\in p \forall p\in P_i).

For example, consider an event for M straight men and N straight women. Then G is the complete bipartite graph K_{M,N}, and a simple solution is to have all the men seated around the inside of a ring-shaped table, all the women around the outside, and to have one set rotate around after each round while the other set stays still. In this case, R = \max(M,N) and T = R |M-N|.

How can you choose the P_i to minimise T?