patternMinor
Minimum number of shopping trips for a group of people to buy presents for each other
Viewed 0 times
numbereachgroupbuyminimumfortripspeoplepresentsother
Problem
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:
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
Solution
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}\s
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}\s
Context
StackExchange Computer Science Q#69615, answer score: 3
Revisions (0)
No revisions yet.