¿Cómo dividir un conjunto en un número dado de subconjuntos disjuntos sujetos a algunas condiciones?

Me dan un conjunto $A\triangleq\{1,\ldots,k\}$ , un número entero $s\leqslant k$ y números enteros no negativos $a_{ij}$ . Mi problema es encontrar $s$ subconjuntos disjuntos $S_j$ de $\{1,\ldots,k\}$ modo que:

1. $\bigcup_{j=1}^s S_j=A$ ; y
2. $|S_j|\leqslant a_{ij}$ para todos $i\in S_j$ y $j=1,\ldots,s$ .

¿Cómo resolver este problema? ¿Es difícil encontrar una solución factible?

Creo que no es fácil resolver el problema porque probé un procedimiento que comienza con algunos $j\in\{1,\ldots,n\}$ y asigna $i\in\{1,\ldots,k\}$ hasta el número de $i$ asignaron a $j$ son mayores que $a_{ij}$ para algunos $i$ asignado. Pero esto no es correcto porque podría quedarme de alguna $i$ que no podría asignarse a ninguna $j$ (debido a su $a_{ij}$ que no podría satisfacerse).

El método de fuerza bruta, cuando tengo que generar todos los subconjuntos de $A$ y probar cada uno, funciona para mí ( $k=8,n=3$ ) pero muy ineficiente.

Este problema es NP-duro por reducción de Vertex Cover.

En el problema de la cubierta de vértices, se nos da un gráfico y un número , y nuestra tarea es determinar si hay algún subconjunto de a lo sumo vértices de modo que cada borde en sea ​​incidente en al menos un vértice en . (Equivalentemente: ¿Es posible matar cada borde en eliminando a lo sumo vértices?)$G = (V, E)$$r$$U$$r$$V$$E$$U$$G$$r$

Primero, dividir en subconjuntos disjuntos de es equivalente a asignar a cada elemento en exactamente una de posibles etiquetas. La idea básica de la reducción es crear una etiqueta para cada vértice en , y "permitir" que a cada borde se le asigne solo una de las dos etiquetas correspondientes a sus puntos finales, en el siguiente sentido: asignar a un borde un correspondiente la etiqueta no introduce ninguna restricción (genuina) sobre qué otros bordes pueden asignarse a la misma etiqueta, mientras que asignar un borde a una etiqueta no correspondiente evita que a cualquier otro borde se le asigne la misma etiqueta, lo que por supuesto tiene el efecto de subir el número de distintas etiquetas requeridas.$A$$s$$A$$s$$S_j$$v_j$$V$

Para construir una instancia de su problema a partir de una instancia de Vertex Cover:$(A, a, s)$$(G, r)$

1. Establezca enY crear un elemento en para cada borde en . (Estos pares pueden considerarse como los enteros ; cualquier biyección entre ellos servirá).$k$$|E|$$(i, j)$$A$$v_iv_j$$E$$1, \dots, k$
2. Establezca ensi o ; de lo contrario, establezca en 1.$a_{(b, c), d}$$|E|$$d=b$$d=c$$a_{(b, c), d}$
3. Establecer .$s=r$

Si es una instancia SÍ de Vertex Cover, entonces es fácil ver que la instancia recién construida de su problema también es una instancia SÍ: simplemente elija las etiquetas correspondientes a los vértices en cualquier solución , y para cada arista asigne el elemento correspondiente cualquiera de las etiquetas o (elija arbitrariamente si se seleccionaron ambas etiquetas). Esta solución utiliza subconjuntos de , y es válida porque los únicos en vigor son los correspondientes$(G, r)$$S_j$$v_j$$U$$v_bv_c \in E$$(b, c) \in A$$S_b$$S_c$$s$$a_{ij}$etiquetas, que tienen el efecto (no) de prevenir más deA los bordes se les asigna la misma etiqueta.$|E|$

Queda por demostrar que una instancia SÍ de su problema implica que el original es una instancia SÍ de Vertex Cover. Esto es un poco más complicado, ya que una solución válida a en general puede asignar un borde una etiqueta no correspondiente , es decir, , lo que significa que no podemos necesariamente "leer off" una cubierta vértice válido a partir de una solución válida .$X=(A, a, s)$$(G, r)$$Y$$X$$(i, j)$$S_m$$m \notin \{i, j\}$$U$$Y$

Sin embargo, asignar una etiqueta no correspondiente tiene un alto costo que limita severamente la estructura de la solución: cada vez que se le asigna un borde dicha etiqueta , con , el hecho que asegura que debe ser el único borde asignado a esta etiqueta. Entonces, en cualquier solución contenga un borde etiquetado de manera no correspondiente , podríamos construir una solución alternativa siguiente manera:$(i, j)$$S_m$$m \notin \{i, j\}$$a_{(i, j), m} = 1$$Y$$(i, j) \mapsto S_m$$Y'$

1. Elija arbitrariamente la nueva etiqueta para como o .$S_z$$(i, j)$$S_i$$S_j$
2. Asigne esta nueva etiqueta. Si esto da como resultado una solución no válida, debe ser porque exactamente a otro borde , ya se le había asignado la etiqueta . En ese caso, establezca y vaya al paso 1.$(i, j)$$(i', j')$$z \notin \{i', j'\}$$S_z$$(i, j) = (i', j')$

El algoritmo anterior debe terminar de una de dos maneras: se encuentra una nueva etiqueta que no introduce contradicción o se encuentra un ciclo completo de vértices. En el primer caso, se encuentra una nueva solución válida con conjuntos , mientras que en el último caso se encuentra una nueva solución válida con conjuntos ; De cualquier manera, hemos construido una nueva solución válida con al menos un borde más asignado a una etiqueta correspondiente . Después de repetir todo este proceso a lo sumoEn ocasiones, habremos producido una solución válida partir de la cual se puede leer una solución al problema original de Vertex Cover .$S_z$$s-1$$s$$|E|$$Y''$

Esta construcción es claramente un tiempo polinomial, por lo que se deduce que su problema es NP-hard.