This problem is NP-hard. To show this, I will first reformulate this (optimization) problem into a decision problem. Then, I reformulate that problem into an equivalent one, from which it is fairly simple to get a reduction from the $k$-coloring problem, which is NP-hard for any $k\geq 3$.
A short formulation of the problem is the following:
Given $n$ persons and a graph $G$ that encodes their 'gift-giving' relations, find the minimum amount of trips required such that all gifts can be bought without ruining any surprises.
However, this is an optimization problem. The class NP is usually defined for descision problems (where the answer to every instance is either YES or NO). A decision variant of this is:
Given $n$ persons and a graph $G$ that encodes their 'gift-giving' relations and an integer $t$, is making at most $t$ trips sufficient to buy all gifts without ruining any surprises?
I define the problem of finding a proper directed $t$-multicoloring of some graph $G=(V,E)$ as finding a multicolor function $c:V\rightarrow \mathcal{P}(C)$ which is proper, where $C$ is some set of $t$ 'colors' (i.e. $|C|=t$) and $\mathcal{P}(C)$ is the power set of $C$ (i.e. the set of all subsets of $C$).
A multicolor function is proper if and only if for every edge $(u\rightarrow v)\in E$, we have that $c(u) \not\subseteq c(v)$.
I claim that the shopping trip problem is equivalent to the problem of deciding the existence of an directed $t$-multicoloring of the same graph $G$.
Proof: If we have a proper directed $t$-multicoloring $c$ for $G$, where we rename the colors such that $C = \{1,\ldots, t\}$ then consider the sequence of $t$ trips $T_1,\ldots, T_t$, where a vertex $v$ goes shopping in trip $T_i$ if and only if $i\in c(v)$. Then, for every edge $(u\rightarrow v)\in E$, we have that there exists a trip $T_i$ such that $u\in T_i$ and $v\notin T_i$, since $c(u) \not\subseteq c(v)$. Therefore, the trips $T_i$ are sufficient to buy all gifts.
If we have a sequence of trips $T_1,\ldots, T_t$, then construct the multi-color function $c$ on color set $C=\{1,\ldots, t\}$ such that $c(u) = \{ i \in \mathbb{N} | u \in T_i\}$. Then, for every edge $(u\rightarrow v)\in E$, there exists a trip $T_i$ such that $u\in T_i$ and $v\notin T_i$ (since $u$ can buy a present for $v$ on some trip), which means that $i\in c(u)$ and $i\notin c(v)$, so $c(u) \not\subseteq c(v)$. $\square$
Finding a proper directed $t$-multicoloring is basically a weird reformulation of a specific case of $k$-coloring. Therefore, I can show a polynomial time reduction from the $\binom{t}{\lfloor t/2 \rfloor}$-coloring problem: Given an undirected graph $G' = (V',E')$, first transform this graph into the directed graph $G=(V,E)$, such that $V=V'$ and $(u\rightarrow v)\in E$ if and only if $(u,v)\in E'$ or $(v,u)\in E'$ (in other words, we change undirected edges into two directed edges).
Consider a largest set $K\subset \mathcal{P}(C)$, such that there exist no $a,b\in K$, $a\neq b$, such that $a\subset b$. The set of all subset of $C$ of size $\lfloor t/2\rfloor$, where $t=|C|$, is such a set. Therefore, the maximum size of such a subset is $\binom{t}{\lfloor t/2 \rfloor}$.
If a proper $t$-multicoloring exists for $G$, then there exists a proper coloring that uses no more than $\binom{t}{\lfloor t/2 \rfloor}$ unequal elements from $\mathcal{P}(C)\ $ (*), so this is a valid $\binom{t}{\lfloor t/2 \rfloor}$-coloring for $G'$.
If a proper $\binom{t}{\lfloor t/2 \rfloor}$-coloring exists for $G'$, then there exists a set $K\subset \mathcal{P}(C)$, $|C|=t$, such that $|K| \geq \binom{t}{\lfloor t/2 \rfloor}$ and there does not exist any $a,b\in K$, $a\neq b$, such that $a\subset b$. So, $G$ has a proper directed $t$-multicoloring.
Therefore, this is a valid polynomial time reduction from $\binom{t}{\lfloor t/2 \rfloor}$-coloring to the present shopping problem with $t$ trips, which means the present shopping problem is NP-hard. Note that the present shopping problem is NP-complete, since we can verify easily if a given list of at most $t$ trips allows us to buy all presents without ruining surprises.
(*): If some multi-coloring $\mathcal{C}$ uses more color-sets than a maximal 'non-subset' multi-coloring $\mathcal{C}^*$, we can 'rename' $\mathcal{C}$ such that it is a superset of $\mathcal{C}^*$. $\mathcal C$ remains proper, as none of the elements from $\mathcal{C}^*$ being adjacent to a different element from $\mathcal{C}^*$ is a problem and none of the color-set were adjacent to each-other in the original $\mathcal{C}$. So, without loss of generality, we can assume $\mathcal{C}^* \subset \mathcal{C}$.
Then, note that 'renaming' $\mathcal{C}\setminus \mathcal{C}^*$ to any subset of $\mathcal{C}^*$ does not ruin the edges between nodes of color-sets $\mathcal{C}\setminus \mathcal{C}^*$, since $\mathcal{C}^*$ contains no elements that are a subset of another. The only thing that is left is to ensure that the edges between $\mathcal{C}\setminus \mathcal{C}^*$ and $\mathcal{C}^*$ do not 'ruin' the coloring.
Consider the following relation $R$ on the color-sets in $\mathcal{C}\cup \mathcal{C}^*$: two color-sets $A$ and $B$ are connected if and only if there exists a pair of vertices $a,b$ such that $a$ has color-set $A$ and $b$ color-set $B$ and $(a,b)\in E$. This relation can be represented by the undirected graph $\mathcal G = (\mathcal{C}\cup \mathcal{C}^*, R)$.
First, we can 'reduce' $\mathcal{C}\setminus \mathcal{C}^*$ by replacing any pair that does not have an edge in $\mathcal G$ by a single color-set. The coloring remains proper, since changing two colorsets that are not adjacent at all into the same color does not introduce any invalid edges. As a result, we have reduced $\mathcal G$ to a complete graph.
This means that if $\mathcal G$ has a less or equal amount of color-sets as $|\mathcal{C}^*|$, the required coloring exists. Otherwise, there exists no proper multi-coloring at all, since $\mathcal{C}^*$ is a largest 'non-subset' set, so we are unable to color this clique. Therefore, the required multi-coloring necessarily exists.
As the complete graph on $n$ nodes $K_n$ is color-able if and only if we have at least $n$ colors, we have that $n$ people can go shopping presents for each other in $t$ trips if and only if $\binom{t}{\lfloor t/2 \rfloor} \geq n$. This means in particular that, if $n\leq 12870$, making only $16$ trips is sufficient. If there are fewer presents to buy, more trips won't be needed, so this is a general upper bound on every solution.
Below is my earlier 'answer', which gives a heuristic algorithm that does not guarantee to get the optimum, but can be computed in polynomial time.
Another way to formulate this problem is to find a covering $C = \{(S_1,T_1), \ldots, (S_m,T_m)\} $ of bipartite graphs on the partitions $(S_i,T_i)$ for some directed graph $G$ with $n$ nodes, such that the amount of partitions (i.e. trips), here $m$, is minimal.
First, some observations, partially coming from other answers:
- The greedy strategy, where we pick a $(S_i,T_i)$ with a bipartite graph where the amount of edges in common with $G$ is maximal, does not lead to an optimal solution (A strong counter-example is the full graph with $6$ nodes, where this strategy fails, no matter which maximum bipartite graph is chosen.).
- The greedy strategy is not optimal for arbitrary acyclic graphs, consider the following graph:
Both for $S_i = \{3,5,6\}$ and $S_i=\{1,3,6\}$ the bipartite graph removes $4$ edges, but only $\{3,5,6\}$ is optimal.
- Any (optimal) greedy algorithm cannot prefer the size of the partition chosen over the amount of cycles (of any size) 'removed' by the partition. To see this, consider the graph with $n+2$ nodes, where there is one cycle of $n$ nodes and every node in the cycle has $2$ additional outgoing edges towards $2$ additional nodes $A,B$, which have no outgoing edges (See figure below for an example where $n=4$). A greedy choice that prefers to maximize the amount of edges over cycles of length $n$ will send all vertices in the cycle on the first trip. This is suboptimal, as this does not remove any edges of the cycle and simply ignoring $A,B$ and removing all edges from the cycle removes all edges towards $A,B$ as well. So any greedy choice that prefers the size of the partition over removing a cycle is not optimal.
Based on these observations, I propose the following greedy choice: Pick $(S_i, T_i)$ such, that the amount of cycles that this trip 'removes' from $G$ is maximal and in case of ties, choose a partition with maximum overlap with $G$ among them (i.e. look at the edges not on cycles).
Since this algorithm isn't different from the 'basic' greedy strategy on acyclic graphs (removing a maximum amount of edges on every trip), this greedy algorithm therefore is not optimal. However, the intuition of removing cycles still makes sense and is an improvement over the basic greedy strategy, so it could be a decent heuristic.
