Minimalna liczba zakupów dla grupy osób, która kupi sobie prezenty

Mamy grupę $n$ osób. Dostajemy listę osób, które muszą kupować prezenty dla kogo w grupie. Każda osoba może potrzebować kupić / otrzymać dowolną liczbę prezentów lub być może wcale. W trakcie zakupów pewna grupa ludzi podróżuje razem do tego samego sklepu i kupuje prezenty wszystkim, którzy nie są obecni w sklepie. Nie mogą kupować prezentów komuś innemu w tej samej podróży na zakupy, ponieważ wtedy nie byłoby to niespodzianką. Osoba może wybrać się na wiele wycieczek zakupowych. Chcemy zminimalizować całkowitą liczbę zakupów koniecznych, aby każdy mógł kupić wszystkie potrzebne prezenty.

Jako przykład rozważmy przypadek, w którym jest 5 osób i każda musi kupić prezenty dla każdej innej osoby w grupie. Niech ludzie będą ponumerowani od 1 do 5. Można to zrobić podczas 4 zakupów, jak pokazano:

• Podróż 1: 1, 2, 3 idź na zakupy

• Podróż 2: 1, 4, 5 idź na zakupy

• Podróż 3: 2, 4 idź na zakupy

• Podróż 4: 3, 5 idź na zakupy

Jak mógłbym rozwiązać ten problem? Oczywistym jest, że dane wejściowe mogą być reprezentowane przez ukierunkowany wykres, ale nie wiem, skąd mam iść. Ktoś poruszył problem z pokrywą biclique , ale chociaż jest podobny, nie odpowiada na to pytanie.

Można myśleć o wejściu w skierowanej wykresie $G$ o $n$ wierzchołkach, przy czym krawędź $(u,v)$ oznacza, że osoba $u$ musi kupować prezent dla osoby $v$ . Celem jest znalezienie zestawu podwójnych $(S_1,T_1),\dots,(S_k,T_k)$ takich, że $k$ jest minimalne, a zestaw krawędzi $E$ wykresu jest podzbiorem $\cup_i (S_i \times T_i)$ . Również w rozszerzenie definicji bicliques skierowanemu na wykresie, biclique$(S_i,T_i)$ zawiera jedynie krawędzie, które mapują$S_i$ do$T_i$ . Różni się to od problemu pokrycia biclique tym, że nie wymagamy, aby każda biclique była subgrafem$G$ (nie wymagamy$S_i \times T_i \subseteq E$ dla każdego$i$ ).

W szczególności przyjmuję odpowiedź, która:

• Pokazuje, że ten problem jest trudny do NP lub
• Przedstawia wielomianowy algorytm czasowy, który dokładnie odpowiada na to pytanie (bez przybliżeń ani górnych granic)

Dla przypomnienia, nigdzie nie widziałem tego problemu, po prostu zastanawiam się nad tym z własnej ciekawości.

Ten problem jest trudny NP . Aby to pokazać, najpierw przeformułuję ten problem (optymalizacji) na problem decyzyjny. Następnie przeformułowuję ten problem na równoważny, z którego dość łatwo jest uzyskać redukcję problemu k- kolorowania, który jest NP-trudny dla dowolnego k ≥ $k$$k\geq 3$ .

Krótkie sformułowanie problemu jest następujące:

Biorąc pod uwagę n osób i wykres G, który koduje ich relacje „dawanie prezentów”, znajdź minimalną wymaganą liczbę podróży, aby wszystkie prezenty można było kupić bez rujnowania niespodzianek.$n$$G$

Jest to jednak problem z optymalizacją. Klasa NP jest zwykle definiowana dla problemów związanych z usuwaniem błędów (gdzie odpowiedź na każde wystąpienie brzmi TAK lub NIE). Wariantem decyzji jest:

Podane n osób i wykres G , który koduje własnej strony „prezentów” stosunki i liczbę całkowitą t , robi co najwyżej t wycieczki wystarczy kupić wszystkie dary bez niszczenia żadnych niespodzianek?$n$$G$$t$$t$

Problem znalezienia właściwego ukierunkowanego t- wielokolorowego$t$ grafu G = ( V , E ) definiuję jako znalezienie funkcji wielokolorowej c : V → P ( C ), która jest właściwa , gdzie C jest jakimś zestawem t „kolorów” ( tj. | C | = t ), a P ( C ) jest zbiorem mocy C (tj. zbiorem wszystkich podzbiorów $G=(V,E)$ $c:V\rightarrow \mathcal{P}(C)$$C$$t$$|C|=t$$\mathcal{P}(C)$$C$$C$). Funkcja wielokolorowa jest właściwa wtedy i tylko wtedy, gdy dla każdej krawędzi ( u → v ) ∈ E mamy to c ( u ) ⊈ c ( v ) .$(u\rightarrow v)\in E$$c(u) \not\subseteq c(v)$

Zastrzeżenia patentowe że problem przelot handlowe odpowiada problemu zdecydowania istnienie skierowanej t -multicoloring$t$ na tym samym wykresie G .$G$

Dowód : jeśli mamy odpowiednio ukierunkowane t - wielokolorowe c dla G , gdzie zmieniamy nazwy kolorów tak, że C = { 1 , … , t }, to rozważmy sekwencję t trip T 1 , … , T t , gdzie wierzchołek v idzie na zakupy w podróży T i wtedy i tylko wtedy, gdy i ∈ c ( v ) . Następnie dla każdej krawędzi ( u → v ) ∈ $t$$c$$G$$C = \{1,\ldots, t\}$$t$$T_1,\ldots, T_t$$v$$T_i$$i\in c(v)$$(u\rightarrow v)\in E$Mamy że istnieje podróży T i taka, że u ∈ ţ I i V U ) ⊈ C ( v ) . Dlatego wycieczki T $T_i$$u\in T_i$∉ T i , ponieważ c $v\notin T_i$$c(u) \not\subseteq c(v)$$T_i$ są wystarczające, aby kupić wszystkie prezenty.

Jeśli mamy sekwencję wyzwalania T 1 , … , T t , to konstruujemy funkcję wielokolorową c na zestawie kolorów C = { 1 , … , t } tak, że c ( u ) = { i ∈ N | U ∈ T I } . Następnie dla każdej krawędzi ( u → v ) ∈ E istnieje trip T i taki, że u $T_1,\ldots, T_t$$c$$C=\{1,\ldots, t\}$$c(u) = \{ i \in \mathbb{N} | u \in T_i\}$$(u\rightarrow v)\in E$$T_i$ T I i V ∉ T í (ponieważ u można kupić prezent dla$u\in T_i$$v\notin T_i$$u$$v$ o pewien TRIP), co oznacza , że ∈ C ( U ) i I ∉ c ( v ) , to C ( U ) ⊈ C ( v ) . $i\in c(u)$$i\notin c(v)$$c(u) \not\subseteq c(v)$$\square$

Znalezienie właściwego skierowaną t -multicoloring jest po prostu dziwne przeformułowanie przypadku określonego w k -coloring. Dlatego mogę pokazać wielomianową redukcję czasu od ($t$$k$⌊ T / 2 ⌋ ) -coloring problemów: Biorąc pod uwagę nieukierunkowane wykresG'=(V',E')najpierw przekształcenia tego wykresu na skierowanej wykresG=(V,E), tak, żeV=V"i(U→v)∈Ewtedy i tylko wtedy, gdy(u,v)∈E′lub(v,$\binom{t}{\lfloor t/2 \rfloor}$$G' = (V',E')$$G=(V,E)$$V=V'$$(u\rightarrow v)\in E$$(u,v)\in E'$$(v,u)\in E'$ (innymi słowy zmieniamy nieukierunkowane krawędzie na dwie skierowane krawędzie).

Rozważ największy zbiór K ⊂ P ( C ) , taki, że nie ma żadnego a , b ∈ K , a ≠ b , taki, że a ⊂ b . Zbiór wszystkich podzbiorów C o rozmiarze ⌊ t / 2 ⌋ , gdzie t = | C | , jest takim zestawem. Dlatego maksymalny rozmiar takiego podzbioru wynosi ($K\subset \mathcal{P}(C)$$a,b\in K$$a\neq b$$a\subset b$$C$$\lfloor t/2\rfloor$$t=|C|$$\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.

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.

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.

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$).