Minimum number of shopping trips for a group of people to buy presents for each other

Question

We have a group of $n$ people. We are given a list of who must buy presents for whom within the group. Each person might need to buy/receive any number of presents, or possibly none at all. In a shopping trip, a subset of the people travel together to the same store, and buy presents for anyone who is not present at the store. They may not buy presents for someone else on the same shopping trip because then it wouldn't be a surprise. A person may go on multiple shopping trips. We want to minimize the total number of shopping trips required for everyone to buy all the presents they need.

As an example, consider the case where there are 5 people, and each must buy presents for every other person in the group. Let the people be numbered 1 to 5. This can be done in 4 shopping trips, as shown:

• Trip 1: 1, 2, 3 go shopping

• Trip 2: 1, 4, 5 go shopping

• Trip 3: 2, 4 go shopping

• Trip 4: 3, 5 go shopping

How would I go about solving this problem? It is obvious that the input can be represented by a directed graph, but I don't know where to go from there. Someone brought up the biclique cover problem, but while similar, it does not answer this question.

We can think of the input as a directed graph $G$ on $n$ vertices, where the edge $(u,v)$ means that person $u$ must buy a present for person $v$. The goal is to find a set of bicliques $(S_1,T_1),\dots,(S_k,T_k)$ such that $k$ is minimal and the edge set $E$ of the graph is a subset of $\cup_i (S_i \times T_i)$. Also, in extending the definition of bicliques to a directed graph, a biclique $(S_i,T_i)$ only contains edges which map $S_i$ to $T_i$. This differs from the biclique cover problem in that we don't require each biclique to be a subgraph of $G$ (we don't require $S_i \times T_i \subseteq E$ for each $i$).

Specifically, I will accept an answer that either:

• Demonstrates that this problem is NP-hard or
• Presents a polynomial time algorithm that answers this question exactly (no approximants or upper bounds)

For the record, I did not see this problem anywhere, I am just wondering about it for my own curiousity.