Como particionar um conjunto em um determinado número de subconjuntos independentes, sujeito a algumas condições?

Recebi um conjunto $A\triangleq\{1,\ldots,k\}$ , um número inteiro $s\leqslant k$ e números inteiros não negativos $a_{ij}$ . Meu problema é encontrar $s$ subconjuntos $S_j$ de $\{1,\ldots,k\}$ modo que:

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

Como resolver este problema? É difícil encontrar uma solução viável?

Acho que não é fácil resolver o problema, porque tentei algum procedimento que começa com $j\in\{1,\ldots,n\}$ e atribui $i\in\{1,\ldots,k\}$ até o número de $i$ atribuído a $j$ é maior que $a_{ij}$ para alguns que $i$ designei. Mas isso não está correto, porque eu poderia ficar com alguns $i$ que não pudessem ser atribuídos a nenhum $j$ (por causa do $a_{ij}$ que não poderia ser satisfeito).

O método da força bruta, quando tenho que gerar todos os subconjuntos de $A$ e testar cada um, funciona para mim ( $k=8,n=3$ ), mas muito ineficiente.

Esse problema é difícil de NP por redução do Vertex Cover.

No problema da cobertura de vértices, recebemos um gráfico e um número , e nossa tarefa é determinar se existe algum subconjunto de no máximo vértices de modo que todas as arestas em sejam incidentes. em pelo menos um vértice em . (Equivalentemente: é possível eliminar todas as arestas em excluindo no máximo vértices?)r U r V E U G $G = (V, E)$$r$$U$$r$$V$$E$$U$$G$$r$

Primeiro, o particionamento em subconjuntos disjuntos é equivalente a atribuição de cada elemento em exatamente uma das possíveis etiquetas. A idéia básica da redução é criar um rótulo para cada vértice em e "permitir" que cada borda seja atribuída apenas a um dos dois rótulos correspondentes aos seus pontos finais, no seguinte sentido: atribuir uma borda a um correspondente A etiqueta não apresenta restrição (genuína) sobre quais outras arestas podem ser atribuídas à mesma etiqueta, enquanto a atribuição de uma borda a uma etiqueta não correspondente impede que qualquer outra borda seja atribuída à mesma etiqueta - o que, obviamente, tem o efeito de aumentar o número de etiquetas distintas necessárias.s A s S j v j$A$$s$$A$$s$$S_j$$v_j$$V$

Para construir uma instância do seu problema a partir de uma instância do Vertex Cover:( G , r $(A, a, s)$$(G, r)$

1. Defina comoE criar um elemento de para cada aresta em . (Esses pares podem ser considerados os números inteiros ; qualquer bijeção entre eles serve.)| E | ( i , j ) A v i v j E 1 , … , $k$$|E|$$(i, j)$$A$$v_iv_j$$E$$1, \dots, k$
2. Defina comose ou ; caso contrário, defina como 1. | E | d = b d = c a ( b , c ) , $a_{(b, c), d}$$|E|$$d=b$$d=c$$a_{(b, c), d}$
3. Defina .$s=r$

Se é uma instância YES do Vertex Cover, é fácil ver que a instância recém- do seu problema também é uma instância YES: basta escolher os rótulos correspondentes aos vértices em qualquer solução e para cada aresta atribua o elemento correspondente que um dos rótulos ou foi selecionado (escolha arbitrariamente se os dois rótulos foram selecionados). Esta solução utiliza subconjuntos, e é válida porque a única em vigor são aqueles para os correspondentesS j v j U v b v c ∈ E ( b , c ) ∈ A S b S c s a i $(G, r)$$S_j$$v_j$$U$$v_bv_c \in E$$(b, c) \in A$$S_b$$S_c$$s$$a_{ij}$rótulos com efeito (não) de impedir mais debordas sendo atribuídas à mesma etiqueta.$|E|$

Resta mostrar que uma instância YES do seu problema implica que o original é uma instância YES da Vertex Cover. Isso é um pouco mais complicado, uma vez que uma solução válida de a pode, em geral, atribuir uma borda um rótulo não correspondente , ou seja, , o que significa que não podemos necessariamente "lido" a cobertura do vértice válida de uma solução válida .( G , r ) Y X ( i , j $X=(A, a, s)$$(G, r)$$Y$$X$$(i, j)$ m ∉ { i , j } U $S_m$$m \notin \{i, j\}$$U$$Y$

No entanto, atribuir um rótulo não correspondente tem um alto custo que limita severamente a estrutura da solução: sempre que uma borda recebe esse rótulo , com , o fato que garante que deve ser a única aresta atribuída a esse rótulo. Portanto, em qualquer solução contenha uma borda não correspondentemente rotulada , poderíamos construir uma solução alternativa seguinte maneira:S m m ∉ { i , j } a ( i , j ) , m = $(i, j)$$S_m$$m \notin \{i, j\}$$a_{(i, j), m} = 1$( i , j ) ↦ S m Y $Y$$(i, j) \mapsto S_m$$Y'$

1. Arbitrariamente escolher o novo rótulo para para ser ou .$S_z$$(i, j)$$S_i$$S_j$
2. Atribua esse novo rótulo. Se isso resultar em uma solução inválida, deve ser porque exatamente uma outra aresta , já recebeu o rótulo . Nesse caso, defina e vá para a etapa 1.$(i, j)$$(i', j')$$z \notin \{i', j'\}$$S_z$$(i, j) = (i', j')$

O algoritmo acima deve terminar de uma de duas maneiras: seja encontrado um novo rótulo que não introduz contradição ou seja encontrado um ciclo completo de vértices. No primeiro caso, uma nova solução válida com conjuntos é encontrada, enquanto no último caso uma nova solução válida com conjuntos é encontrada; de qualquer maneira, construímos uma nova solução válida com pelo menos mais uma borda atribuída a um rótulo correspondente . Depois de repetir todo esse processo no máximovezes, teremos produzido uma solução válida partir da qual uma solução para o problema original da Vertex Cover pode ser lida.$S_z$$s-1$$s$$|E|$$Y''$

Essa construção é claramente um tempo polinomial; portanto, seu problema é difícil para o NP.