Nombre minimum de voyages pour un groupe de personnes à acheter des cadeaux les uns pour les autres

Question

Nous avons un groupe de personnes N $. On nous donne une liste de qui doit acheter des cadeaux pour qui au sein du groupe. Chaque personne peut avoir besoin d'acheter / recevoir un nombre de cadeaux, ou peut-être aucune. Lors d'un voyage de shopping, un sous-ensemble de personnes voyagent ensemble dans le même magasin et acheter des cadeaux pour quiconque n'est pas présent au magasin. Ils peuvent ne pas acheter de cadeaux pour quelqu'un d'autre lors du même voyage de shopping, car ce ne serait pas une surprise. Une personne peut faire plusieurs sorties de magasinage. Nous voulons minimiser le nombre total de voyages d'achat requis pour que tout le monde puisse acheter tous les cadeaux dont ils ont besoin.

Par exemple, considérez le cas où il y a 5 personnes, et chacun doit acheter des cadeaux pour toutes les autres personnes du groupe. Que les gens soient numérotés de 1 à 5. Cela peut être fait en 4 voyages, comme indiqué:

• Trip 1: 1, 2, 3 faire du shopping

• Trip 2: 1, 4, 5 Allez faire du shopping

• Trip 3: 2, 4 allez faire du shopping

• Trip 4: 3, 5 allez faire du shopping

Comment pourrais-je résoudre ce problème? Il est évident que l'entrée peut être représentée par un graphique dirigé, mais je ne sais pas où aller à partir de là. Quelqu'un a élevé le Problème de couverture biclique, mais bien que similaire, il ne répond pas à cette question.

Nous pouvons considérer l'entrée comme un graphique dirigé $ g $ sur $ n $ Vertices, où le bord $ (u, v) $ signifie que la personne $ u $ doit acheter un cadeau pour la personne $ v $. L'objectif est de trouver un ensemble de bicliques $ (s_1, t_1), Dots, (s_k, t_k) $ tels que $ k $ est minimal et le jeu de bord $ e $ du graphique est un sous-ensemble de $ cup_i ( S_i Times T_i) $. De plus, en étendant la définition de Bicliques à un graphique dirigé, un biclique $ (s_i, t_i) $ ne contient que des bords qui mappent $ s_i $ à $ t_i $. Cela diffère du problème de la couverture biclique en ce que nous ne nécessitons pas que chaque biclique soit un sous-graphique de $ g $ (nous ne nécessitons pas $ s_i Times t_i subseteq e $ pour chaque $ i $).

Plus précisément, j'accepterai une réponse qui: soit:

• Démontre que ce problème est du NP-dure ou
• Présente un algorithme de temps polynomial qui répond exactement à cette question (pas d'approximants ou de limites supérieures)

Pour mémoire, je n'ai vu ce problème nulle part, je me demande juste à ce sujet pour ma propre curiosité.