Comment partitionner un ensemble en un nombre donné de sous-ensembles disjoints soumis à certaines conditions?

On me donne un ensemble $A\triangleq\{1,\ldots,k\}$ , un entier $s\leqslant k$ et des entiers non négatifs $a_{ij}$ . Mon problème est de trouver $s$ sous - ensembles disjoints $S_j$ de $\{1,\ldots,k\}$ tel que:

1. $\bigcup_{j=1}^s S_j=A$ ; et
2. $|S_j|\leqslant a_{ij}$ pour tous les $i\in S_j$ et $j=1,\ldots,s$ .

Comment résoudre ce problème? Est-il difficile de trouver une solution réalisable?

Je pense qu'il n'est pas facile de résoudre le problème car j'ai essayé une procédure qui commence par certains $j\in\{1,\ldots,n\}$ et assigne $i\in\{1,\ldots,k\}$ jusqu'au nombre des $i$ attribués à $j$ sont supérieurs à $a_{ij}$ pour certains $i$ attribués. Mais ce n'est pas correct car je pourrais me retrouver avec des $i$ qui ne pourraient être attribués à aucun $j$ (à cause de leur $a_{ij}$ qui pourrait ne pas être satisfait).

La méthode de la force brute, quand je dois générer tous les sous-ensembles de $A$ et tester chacun, fonctionne pour moi ( $k=8,n=3$ ) mais très inefficace.

Ce problème est NP-difficile par réduction de Vertex Cover.

Dans le problème de couverture de , on nous donne un graphique et un nombre , et notre tâche est de déterminer s'il existe un sous-ensemble d'au plus sommets de telle sorte que chaque bord de soit incident sur au moins un sommet en . (De manière équivalente: est-il possible de tuer chaque arête de en supprimant au plus sommets?)$G = (V, E)$$r$$U$$r$$V$$E$$U$$G$$r$

Premièrement, le partitionnement de en sous-ensembles disjoints équivaut à affecter à chaque élément de exactement l'un des labels possibles. L'idée de base de la réduction est de créer une étiquette pour chaque sommet dans , et de "n'autoriser" à affecter à chaque arête qu'une seule des deux étiquettes correspondant à ses extrémités, dans le sens suivant: attribuer à une arête un correspondant label n'introduit aucune contrainte (authentique) sur les autres bords auxquels la même étiquette peut être affectée, tandis que l'attribution d'un bord à une étiquette non correspondante empêche que tout autre bord se voit attribuer la même étiquette - ce qui a bien sûr pour effet d'augmenter le nombre d'étiquettes distinctes requises.$A$$s$$A$$s$$S_j$$v_j$$V$

Pour construire une instance de votre problème à partir d'une instance de Vertex Cover:$(A, a, s)$$(G, r)$

1. Réglez surEt créer un élément dans pour chaque bord dans . (Ces paires peuvent être considérées comme les entiers ; toute bijection entre elles fera l'affaire.)$k$$|E|$$(i, j)$$A$$v_iv_j$$E$$1, \dots, k$
2. Réglez sursi ou ; sinon, définissez sur 1.$a_{(b, c), d}$$|E|$$d=b$$d=c$$a_{(b, c), d}$
3. Définissez .$s=r$

Si est une instance YES de Vertex Cover, alors il est facile de voir que l'instance juste construite de votre problème est également une instance YES: il suffit de choisir les étiquettes correspondant aux sommets dans n'importe quelle solution , et pour chaque arête affectez l'élément correspondant selon l'une des étiquettes ou été choisie (choisissez arbitrairement si les deux étiquettes ont été choisies). Cette solution utilise sous-ensembles et est valide car les seuls en vigueur sont ceux des correspondants$(G, r)$$S_j$$v_j$$U$$v_bv_c \in E$$(b, c) \in A$$S_b$$S_c$$s$$a_{ij}$étiquettes, qui ont pour (non) effet d'empêcher plus debords étant affectés de la même étiquette.$|E|$

Il reste à montrer qu'une instance YES de votre problème implique que l'original est une instance YES de Vertex Cover. C'est un peu plus compliqué, car une solution valide à peut en général attribuer à un bord une étiquette non correspondante , c'est-à-dire , ce qui signifie que nous ne pouvons pas nécessairement « lire sur » une couverture de sommet valide à partir d' une solution valable .$X=(A, a, s)$$(G, r)$$Y$$X$$(i, j)$$S_m$$m \notin \{i, j\}$$U$$Y$

Cependant, l'attribution d'une étiquette non correspondante a un coût élevé qui limite considérablement la structure de la solution: chaque fois qu'une arête est affectée à une telle étiquette , avec , le fait qu'un assure qu'il doit être le seul bord affecté à cette étiquette. Ainsi, dans toute solution contenant un tel bord non étiqueté de manière correspondante , nous pourrions construire une solution alternative comme suit:$(i, j)$$S_m$$m \notin \{i, j\}$$a_{(i, j), m} = 1$$Y$$(i, j) \mapsto S_m$$Y'$

1. Choisissez arbitrairement la nouvelle étiquette pour que soit ou .$S_z$$(i, j)$$S_i$$S_j$
2. Attribuez cette nouvelle étiquette. Si cela aboutit à une solution invalide, ce doit être parce qu'exactement un autre bord , avait déjà reçu le label . Dans ce cas, définissez et passez à l'étape 1.$(i, j)$$(i', j')$$z \notin \{i', j'\}$$S_z$$(i, j) = (i', j')$

L'algorithme ci-dessus doit se terminer de deux manières: soit une nouvelle étiquette est trouvée qui n'introduit aucune contradiction, soit un cycle complet de sommets est trouvé. Dans le premier cas, une nouvelle solution valide avec ensembles est trouvée, tandis que dans le dernier cas, une nouvelle solution valide avec ensembles est trouvée; de toute façon, nous avons construit une nouvelle solution valide avec au moins un bord supplémentaire affecté à une étiquette correspondante . Après avoir répété tout ce processusfois, nous aurons produit une solution valide partir de laquelle une solution au problème Vertex Cover d'origine peut être lue.$S_z$$s-1$$s$$|E|$$Y''$

Cette construction est clairement polynomiale, il s'ensuit que votre problème est NP-difficile.