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

10

Mamy grupę nn 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 GG o nn wierzchołkach, przy czym krawędź ( U , V )(u,v) oznacza, że osoba uu musi kupować prezent dla osoby vv . Celem jest znalezienie zestawu podwójnych ( S 1 , T 1 ) , , ( S k , T k )(S1,T1),,(Sk,Tk) takich, że kk jest minimalne, a zestaw krawędzi EE wykresu jest podzbiorem i ( S i × T ja)i(Si×Ti) . Również w rozszerzenie definicji bicliques skierowanemu na wykresie, biclique ( S I , T i )(Si,Ti) zawiera jedynie krawędzie, które mapują Ś ISi do T ıTi . Różni się to od problemu pokrycia biclique tym, że nie wymagamy, aby każda biclique była subgrafem GG (nie wymagamy S i × T iESi×TiE dla każdego ii ).

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.

Riley
źródło

Odpowiedzi:

2

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 3kk3 .

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.nG

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?nGtt

Problem znalezienia właściwego ukierunkowanego t- wielokolorowegot 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 CG=(V,E) c:VP(C)Ct| do| =tP.( C)dodo). 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 v ) Ec(u)c(v)

Zastrzeżenia patentowe że problem przelot handlowe odpowiada problemu zdecydowania istnienie skierowanej t -multicoloringt 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 ) EtcGC={1,,t}tT1,,TtvTiic(v)(uv)EMamy że istnieje podróży T i taka, że u ţ I i V U ) C ( v ) . Dlatego wycieczki T iTiuTiT i , ponieważ c (vTic(u)c(v)Ti 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 T1,,TtcC={1,,t}c(u)={iN|uTi}(uv)ETi T I i V T í (ponieważ u można kupić prezent dla vuTivTiuv o pewien TRIP), co oznacza , że C ( U ) i I c ( v ) , to C ( U ) C ( v ) . ic(u)ic(v)c(u)c(v)

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 ( ttkT / 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(Uv)Ewtedy i tylko wtedy, gdy(u,v)Elub(v,u(tt/2)G=(V,E)G=(V,E)V=V(uv)E(u,v)E ) E (v,u)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 ( tKP(C)a,bKababCt/2t=|C|t/2)(tt/2).

If a proper tt-multicoloring exists for GG, then there exists a proper coloring that uses no more than (tt/2)(tt/2) unequal elements from P(C) P(C)  (*), so this is a valid (tt/2)(tt/2)-coloring for GG.

If a proper (tt/2)(tt/2)-coloring exists for GG, then there exists a set KP(C)KP(C), |C|=t|C|=t, such that |K|(tt/2)|K|(tt/2) and there does not exist any a,bKa,bK, abab, such that abab. So, GG has a proper directed tt-multicoloring.

Therefore, this is a valid polynomial time reduction from (tt/2)(tt/2)-coloring to the present shopping problem with tt 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 tt trips allows us to buy all presents without ruining surprises.


(*): If some multi-coloring CC uses more color-sets than a maximal 'non-subset' multi-coloring CC, we can 'rename' CC such that it is a superset of CC. CC remains proper, as none of the elements from CC being adjacent to a different element from CC is a problem and none of the color-set were adjacent to each-other in the original CC. So, without loss of generality, we can assume CCCC.

Then, note that 'renaming' CCCC to any subset of CC does not ruin the edges between nodes of color-sets CCCC, since CC contains no elements that are a subset of another. The only thing that is left is to ensure that the edges between CCCC and CC do not 'ruin' the coloring.

Consider the following relation RR on the color-sets in CCCC: two color-sets AA and BB are connected if and only if there exists a pair of vertices a,ba,b such that aa has color-set AA and bb color-set BB and (a,b)E(a,b)E. This relation can be represented by the undirected graph G=(CC,R)G=(CC,R).

First, we can 'reduce' CCCC by replacing any pair that does not have an edge in GG 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 GG to a complete graph.

This means that if GG has a less or equal amount of color-sets as |C||C|, the required coloring exists. Otherwise, there exists no proper multi-coloring at all, since CC 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 nn nodes KnKn is color-able if and only if we have at least nn colors, we have that nn people can go shopping presents for each other in tt trips if and only if (tt/2)n(tt/2)n. This means in particular that, if n12870n12870, making only 1616 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={(S1,T1),,(Sm,Tm)}C={(S1,T1),,(Sm,Tm)} of bipartite graphs on the partitions (Si,Ti)(Si,Ti) for some directed graph GG with nn nodes, such that the amount of partitions (i.e. trips), here mm, is minimal.

First, some observations, partially coming from other answers:

  • The greedy strategy, where we pick a (Si,Ti)(Si,Ti) with a bipartite graph where the amount of edges in common with GG is maximal, does not lead to an optimal solution (A strong counter-example is the full graph with 66 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 Si={3,5,6}Si={3,5,6} and Si={1,3,6}Si={1,3,6} the bipartite graph removes 44 edges, but only {3,5,6}{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+2n+2 nodes, where there is one cycle of nn nodes and every node in the cycle has 22 additional outgoing edges towards 22 additional nodes A,BA,B, which have no outgoing edges (See figure below for an example where n=4n=4). A greedy choice that prefers to maximize the amount of edges over cycles of length nn 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,BA,B and removing all edges from the cycle removes all edges towards A,BA,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 (Si,Ti)(Si,Ti) such, that the amount of cycles that this trip 'removes' from GG is maximal and in case of ties, choose a partition with maximum overlap with GG 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.

Discrete lizard
źródło
1
You state "If a tt-multicoloring exists for GG, then this coloring uses no more than (tt/2)(tt/2) unequal elements from P(C)P(C)". This statement is false. In the trivial example of 3 disconnected nodes a,b,ca,b,c there exists a 2-multicoloring vv, where v(a)={1},v(b)={2},v(c)={1,2}v(a)={1},v(b)={2},v(c)={1,2}. This is a proper 2-multicoloring which uses more than (21)=2(21)=2 distinct elements. Did you mean to say "If a tt-multicoloring exists for GG, then one such coloring uses no more than (tt/2)(tt/2) unequal elements from P(C)P(C)"?
Riley
Indeed, that is what I meant. Another way to look at it is that if it is a minimal t-multicoloring (i.e. this GG isn't (t1)(t1)-multicolorable), it uses exactly (tt/2)(tt/2) elements. Clearly, the example you give is not a counterexample to the correct reformulation.
Discrete lizard
No wait. It does not use exactly (tt/2)(tt/2) elements, but at most.
Discrete lizard
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 KK meeting the requirement of size, and that there exist no a,bKa,bK such that abab.
Riley
@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 P(C)P(C) has size (tt/2)(tt/2), we might as well consider that set as a color set and we get the coloring problem.
Discrete lizard
2

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)G=(V,E) is the original directed graph in which an edge uvuv indicates that person uu needs to buy person vv a gift, then create an undirected graph H=(X,Y)H=(X,Y) in which there is a vertex xuvxuv for each edge uvuv in GG and an (undirected) edge xuvxvwxuvxvw whenever uvuv and vwvw are both (directed) edges in GG (if vv buys some ww a gift during a trip, then no one can buy vv a gift during that same trip). A vertex colouring of HH is a partition of the necessary purchases (vertices in HH) 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.

j_random_hacker
źródło
This answer is brilliant; it's just what I was looking for. In analyzing the time complexity of this algorithm, there are at most n2n vertices (presents) and (2n3)(n2n)2 edges. When I look up an algorithm on graph coloring all I find is O(2nn) 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?
Riley
1
@Riley Probably not, deciding k-colourability, k3 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.
Discrete lizard
@ Discrete lizard : ​ Where in those lecture notes do they give such a reduction? ​ ​ ​ ​
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.
Discrete lizard
1
@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.
Riley
0

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.

gnasher729
źródło
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}}.
Riley
Absolutely no proof. Greedy algorithm + making different random choices would improve your chances a bit but wouldn't do 4 trips.
gnasher729
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).
Riley
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}}.
Riley
-1

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 p1 and order everyone accordingly, so child(p1)=p2, etc. You put all podd into one group, and all peven into another group. For the last person pn=parent(p1), so you don't want this person to be in the same group with p1. If n is even, it is not a problem. Else, you need one additional group, that can be just pn 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, pk=parent(p1) 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).

ilke444
źródło
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.
D.W.
That's true, my solution is for a sub-case of the problem where i,fan_in(vi)=fan_out(vi)=1.
ilke444
Yes, I was not asking for permutations specifically. Please see the updated question where I clarify a few things.
Riley