Eu segui o link da pergunta, e a redução ali produz gráficos cujas bordas têm uma coloração natural, de modo que cada Kn presente no gráfico é um "arco-íris Kn " (tem exatamente uma borda de cada cor). Em outras palavras, podemos ajustar facilmente a redução nesse papel para reduzir ao seu problema, em vez de reduzir à partição para o problema de Kn s: basta atribuir uma cor a cada borda de acordo com essa coloração natural e, em seguida, o gráfico pode ser particionado em "arco-íris Kn s" se, e somente se, puder ser particionado em Kn s.
A estrutura básica da redução nesse documento pode ser realizada com as três etapas a seguir:
- Crie muitas cópias de um gráfico específico Hn,p .
- Identifique certas partes de algumas cópias de Hn,p entre si (ou seja, mescle vértices / arestas entre várias cópias diferentes de Hn,p ).
- Remova certos vértices / arestas de algumas cópias.
O gráfico Hn,p tem como vértices o conjunto de vetores comprimento n módulo p para o qual os componentes somam 0 mod p . As arestas conectam todos os dois vértices que diferem em apenas dois componentes com diferenças de +1 e −1 nesses dois componentes.
Proponho a seguinte coloração para este gráfico: atribua uma cor a cada aresta de acordo com sua direção. Se x e y são vértices adjacentes, então x−y é um vetor com n−2 componentes iguais a 0 , um componente igual a 1 e um componente igual a −1 . Em outras palavras, para cada aresta (x,y) existem (n2) opções para as quais os componentes dex−ysão diferentes de zero. Se atribuirmos uma cor exclusiva a cada uma dessas opções, teremos uma cor para todas as arestas, de modo que todas as arestas na mesma direção tenham a mesma cor. É bastante fácil para verificar que não há duas bordas em umKnemHn,psão na mesma direcção. Portanto, todoKnemHn,pé um arco-írisKnsob essa coloração.
Quando seguimos a redução, usamos essa coloração para todas as cópias de Hn,p . Portanto, no final da etapa 1 da lista acima, todo Kn no gráfico é um arco-íris Kn .
Na etapa 2 da lista acima, identificamos alguns vértices / arestas entre si. Em particular, na redução sempre identificamos um Kn com outro Kn . Mas nesta situação (onde toda a Kn s são de uma cópia do Hn,p ), cada Kn ou é uma tradução do "padrão Kn " qual o papel chama K ou uma tradução de −K . Portanto, estamos identificando dois Kn s paralelos ou dois Kns que são "flips" um do outro. Nos dois casos, as arestas identificadas nos dois Kn s são paralelas e, portanto, têm a mesma cor. Por exemplo, veja a Figura 2 no documento; as arestas identificadas são sempre paralelas. Portanto, como nunca tentamos identificar duas arestas de cores diferentes, a coloração no final da etapa 1 da lista acima pode ser naturalmente estendida para uma coloração no final da etapa 2. Identificar certos vértices / arestas juntos não cria qualquer novo Kn s, então ainda é o caso, no final desta etapa, de que cada Kn é um arco-íris Kn .
Finalmente no passo 3 que remover alguns vértices / bordas, que também não cria qualquer nova Kn s. Assim, temos nossa propriedade desejada: sob a coloração que forneci, todo Kn no gráfico gerado por essa redução é um arco-íris Kn .