Particionamento de arestas em triângulos arco-íris
Gostaria de saber se o seguinte problema é NP-difícil.
Insira: G = ( V, E)G=(V,E) um gráfico simples e uma coloração f: E→ { 1 , 2 , 3 }f:E→{1 1,2,3} das arestas ( ff não verifica nenhuma propriedade específica).
Pergunta: é possível particionar EE em | E| / 3|E|/3 triângulos, de modo que cada triângulo tenha uma aresta de cada cor?
Sei que, sem as cores, o problema de "particionamento de arestas" de um gráfico em KnKn , é NP-difícil (consulte A NP-Completude de alguns problemas de partição de arestas ), mas com as cores que não conheço.n ≥ 3n≥3
Eu também estaria interessado em um resultado para a particionamento da borda no arco-íris , com uma constante. Obviamente, neste caso, o problema se torna: cKcKccc
Entrada: um gráfico simples e uma coloração das arestas ( não verifica nenhuma propriedade específica) .f : E → { 1 , … , c ( c - 1 ) / 2 } fG=(V,E)G=(V,E)f:E→{1,…,c(c−1)/2}f:E→{1,…,c(c−1)/2}ff
Pergunta: é possível particionar em ', de modo que cada clique tenha uma aresta de cada cor?| E | / ( c ( c - 1 ) / 2 ) K c K cEE|E|/(c(c−1)/2)|E|/(c(c−1)/2) KcKcKcKc
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 KnKn presente no gráfico é um "arco-íris KnKn " (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 KnKn 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 KnKn s" se, e somente se, puder ser particionado em KnKn 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,pHn,p .
Identifique certas partes de algumas cópias de Hn,pHn,p entre si (ou seja, mescle vértices / arestas entre várias cópias diferentes de Hn,pHn,p ).
Remova certos vértices / arestas de algumas cópias.
O gráfico Hn,pHn,p tem como vértices o conjunto de vetores comprimento nn módulo pp para o qual os componentes somam 00 mod pp . As arestas conectam todos os dois vértices que diferem em apenas dois componentes com diferenças de +1+1 e −1−1 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 xx e yy são vértices adjacentes, então x−yx−y é um vetor com n−2n−2 componentes iguais a 00 , um componente igual a 11 e um componente igual a −1−1 . Em outras palavras, para cada aresta (x,y)(x,y) existem (n2)(n2) opções para as quais os componentes dex−yx−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 umKnKnemHn,pHn,psão na mesma direcção. Portanto, todoKnKnemHn,pHn,pé um arco-írisKnKnsob essa coloração.
Quando seguimos a redução, usamos essa coloração para todas as cópias de Hn,pHn,p . Portanto, no final da etapa 1 da lista acima, todo KnKn no gráfico é um arco-íris KnKn .
Na etapa 2 da lista acima, identificamos alguns vértices / arestas entre si. Em particular, na redução sempre identificamos um KnKn com outro KnKn . Mas nesta situação (onde toda a KnKn s são de uma cópia do Hn,pHn,p ), cada KnKn ou é uma tradução do "padrão KnKn " qual o papel chama KK ou uma tradução de −K−K . Portanto, estamos identificando dois KnKn s paralelos ou dois KnKns que são "flips" um do outro. Nos dois casos, as arestas identificadas nos dois KnKn 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 KnKn s, então ainda é o caso, no final desta etapa, de que cada KnKn é um arco-íris KnKn .
Finalmente no passo 3 que remover alguns vértices / bordas, que também não cria qualquer nova KnKn s. Assim, temos nossa propriedade desejada: sob a coloração que forneci, todo KnKn no gráfico gerado por essa redução é um arco-íris KnKn .