10
$\begingroup$

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.

$\endgroup$
2
+100
$\begingroup$

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: hard-acyclic 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.
    4-cycle

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.

$\endgroup$
  • 1
    $\begingroup$ You state "If a $t$-multicoloring exists for $G$, then this coloring uses no more than $\binom{t}{\lfloor t/2 \rfloor}$ unequal elements from $\mathcal{P}(C)$". This statement is false. In the trivial example of 3 disconnected nodes $a,b,c$ there exists a 2-multicoloring $v$, where $v(a)=\{1\},v(b)=\{2\},v(c)=\{1,2\}$. This is a proper 2-multicoloring which uses more than $\binom{2}{1}=2$ distinct elements. Did you mean to say "If a $t$-multicoloring exists for $G$, then one such coloring uses no more than $\binom{t}{\lfloor t/2 \rfloor}$ unequal elements from $\mathcal{P}(C)$"? $\endgroup$ – Riley Feb 12 '17 at 14:09
  • $\begingroup$ Indeed, that is what I meant. Another way to look at it is that if it is a minimal t-multicoloring (i.e. this $G$ isn't $(t-1)$-multicolorable), it uses exactly $\binom{t}{\lfloor t/2 \rfloor}$ elements. Clearly, the example you give is not a counterexample to the correct reformulation. $\endgroup$ – Discrete lizard Feb 12 '17 at 17:45
  • $\begingroup$ No wait. It does not use exactly $\binom{t}{\lfloor t/2\rfloor}$ elements, but at most. $\endgroup$ – Discrete lizard Feb 12 '17 at 19:55
  • $\begingroup$ I can understand how that revised statement makes intuitive sense, but can you prove it? Maybe you could somehow show that any t-multicoloring may be "improved" so that all multicolors are elements of some set $K$ meeting the requirement of size, and that there exist no $a,b\in K$ such that $a\subset b$. $\endgroup$ – Riley Feb 12 '17 at 23:57
  • $\begingroup$ @Riley I'm not sure what you mean, which statement do you want me to elaborate? I've updated my answer such that it states what your original comment suggested. The rest of the proof remains unaffected. As for the relation of the multi and original color problem, the key idea is that the multi-coloring can be seen as not having adjacent 'subsets'. Since the largest 'non-pairwise subsetting' subset of $\mathcal{P}(C)$ has size $\binom{t}{\lfloor t/2\rfloor}$, we might as well consider that set as a color set and we get the coloring problem. $\endgroup$ – Discrete lizard Feb 13 '17 at 8:12
2
+50
$\begingroup$

I can see how to reduce this problem to Graph Colouring, which gives you a tool for solving the problem (for small instances!), but not yet how to reduce in the other direction (which would establish NP-hardness).

The basic idea is to build a graph that contains a vertex for every purchase, and an edge between any two purchases that cannot occur on the same trip; we then look to group the purchases into the smallest possible number of groups ("trips"), such that no two purchases in the same group would conflict. Specifically, if $G = (V, E)$ is the original directed graph in which an edge $uv$ indicates that person $u$ needs to buy person $v$ a gift, then create an undirected graph $H = (X, Y)$ in which there is a vertex $x_{uv}$ for each edge $uv$ in $G$ and an (undirected) edge $x_{uv}x_{vw}$ whenever $uv$ and $vw$ are both (directed) edges in $G$ (if $v$ buys some $w$ a gift during a trip, then no one can buy $v$ a gift during that same trip). A vertex colouring of $H$ is a partition of the necessary purchases (vertices in $H$) into trips (colours) that don't conflict (share an edge), and a vertex colouring of minimum size takes the fewest possible trips.

It might be possible to go in the other direction (reduce Graph Colouring, or some other NP-hard problem, to your problem, and thereby establish its NP-hardness), by adapting a reduction from 3SAT to Graph Colouring (as, e.g., detailed on p. 10 of Jeff Erickson's notes), but I haven't attempted this myself.

$\endgroup$
  • $\begingroup$ This answer is brilliant; it's just what I was looking for. In analyzing the time complexity of this algorithm, there are at most $n^2-n$ vertices (presents) and $\frac{(2n-3)(n^2-n)}{2}$ edges. When I look up an algorithm on graph coloring all I find is $O(2^nn)$ for a graph with $n$ vertices. Is there a more efficient algorithm in this case because there is a polynomial upper bound on the number of edges? $\endgroup$ – Riley Feb 5 '17 at 19:00
  • 1
    $\begingroup$ @Riley Probably not, deciding $k$-colourability, $k\geq 3$ for a graph with maximum degree $3$ is already NP-hard. See these [lecture notes](www-sop.inria.fr/members/Frederic.Havet/Cours/coloration.pdf) for a reduction from 3-SAT to graphs with maximum degree 3. $\endgroup$ – Discrete lizard Feb 6 '17 at 10:02
  • $\begingroup$ @ Discrete lizard : ​ Where in those lecture notes do they give such a reduction? ​ ​ ​ ​ $\endgroup$ – user12859 Feb 7 '17 at 11:04
  • $\begingroup$ Why is this answer accepted? It neither shows NP-hardness nor a 'most optimal' algorithm or even an efficient algorithm, as far as I can see. $\endgroup$ – Discrete lizard Feb 7 '17 at 17:11
  • 1
    $\begingroup$ @Discretelizard Okay. I didn't think that the question implied I am looking for a P time algorithm, especially given the possibility that this problem is NP-hard. But I can make that point more explicit in the original question. I will unmark this answer as correct, and add a 100 point bounty (it turns out the second one has to be 100 if on the same question, but I'm willing to offer it because they're just imaginary internet points, right? :) ) again to anyone who can either show this problem is NP-hard, OR find a polynomial time algorithm that solves it. $\endgroup$ – Riley Feb 9 '17 at 23:08
0
$\begingroup$

It's the kind of problem where I would be very worried if my boss asked my to implement an algorithm that is guaranteed to find an optimal solution in reasonable time.

To find a not necessarily optimal solution: Given any set of people and presents to buy, we can count how many presents a group of people can buy on a shopping trip. So start with an empty group (which can buy 0 presents). For each person not in the group, determine how many presents can be bought if that person is added to the group. If there is any person that we can add without decreasing the number of presents, pick at random one of those that increase the number of presents bought by the maximum amount, until adding any person would reduce the number of presents bought. Then do that shopping trip and start all over until all presents are bought.

I'd repeat a few times, picking different people "at random" in case that finds a better solution.

In the example, five people having to buy a present for each other, this finds a solution in four trips, which is optimal; if we didn't add persons to a trip that leave the number of presents unchanged without improving it, we would have five trips. And 6 people require 5 trips.

$\endgroup$
  • $\begingroup$ So in other words, you are greedily choosing shopping trips according to how many presents would be bought. Could you prove that this procedure necessarily results in the minimum possible number of shopping trips? If it does, you worked through the example of 6 people incorrectly. 6 people only require 4 shopping trips: $\{\{1,2,3\},\{1,4,5\},\{2,4,6\},\{3,5,6\}\}$. $\endgroup$ – Riley Feb 4 '17 at 15:54
  • $\begingroup$ Absolutely no proof. Greedy algorithm + making different random choices would improve your chances a bit but wouldn't do 4 trips. $\endgroup$ – gnasher729 Feb 4 '17 at 16:15
  • $\begingroup$ I've tested the claim that the problem is greedy, and it fails. Even if you test every possible shopping trip rather than adding people one by one, you still get 5 trips: $\{\{1,2,3\},\{4,5,6\},\{1,4\},\{2,5\},\{3,6\}\}$. The greedy approach would like the second shopping trip to buy 9 presents, but in the optimal solution the second shopping trip buys 8 presents (assuming it goes in the order listed above). $\endgroup$ – Riley Feb 4 '17 at 19:48
  • $\begingroup$ In fact, the greedy approach doesn't even solve the case of 5 people in 4 shopping trips either: $\{\{1,2\},\{3,4\},\{5\},\{1,3\},\{2,4\}\}$. $\endgroup$ – Riley Feb 4 '17 at 20:08
-1
$\begingroup$

Assume that you order the people based on who they are receiving from (parent), and who they are giving to (child). Since everyone gives one present and receives one present, parent-child function is one-to-one.

You never want to put the parent and the child into the same group. You start with a random person $p_1$ and order everyone accordingly, so $child(p_1)=p_2$, etc. You put all $p_{odd}$ into one group, and all $p_{even}$ into another group. For the last person $p_n=parent(p_1)$, so you don't want this person to be in the same group with $p_1$. If $n$ is even, it is not a problem. Else, you need one additional group, that can be just $p_n$ by itself, in the simplest case.

This algorithm assumes everyone is connected. But it does not need to be the case. If there are multiple disconnected cycles, in other words, if at some point, $p_k=parent(p_1)$ where $k!=n$, then you finish that circle and start with a new one, following the same algorithm. As long as you don't merge the odds and evens of the same cycle, you can merge disconnected cycles.

This algorithm ends up with at most 2 rounds (for even $n$) and 3 rounds (for odd $n$).

$\endgroup$
  • $\begingroup$ It seems this approach only solves the problem for the case where everyone gives one present and receives one present, i.e., where the graph is a permutation. I'm not sure that the question meant to ask only about that special case -- let's see what the OP has to say about that. $\endgroup$ – D.W. Jan 31 '17 at 22:30
  • $\begingroup$ That's true, my solution is for a sub-case of the problem where $\forall i, fan\_in(v_i)=fan\_out(v_i)=1$. $\endgroup$ – ilke444 Jan 31 '17 at 23:36
  • $\begingroup$ Yes, I was not asking for permutations specifically. Please see the updated question where I clarify a few things. $\endgroup$ – Riley Feb 1 '17 at 0:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.