Particionamento de arestas em triângulos arco-íris

9

Gostaria de saber se o seguinte problema é NP-difícil.

Insira: G=(V,E) um gráfico simples e uma coloração f:E{1 1,2,3} das arestas ( f não verifica nenhuma propriedade específica).

Pergunta: é possível particionar E em |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 Kn , é NP-difícil (consulte A NP-Completude de alguns problemas de partição de arestas ), mas com as cores que não conheço.n3

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: cKcc

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)f:E{1,,c(c1)/2}f

Pergunta: é possível particionar em ', de modo que cada clique tenha uma aresta de cada cor?| E | / ( c ( c - 1 ) / 2 ) K c K cE|E|/(c(c1)/2) KcKc

user32018
fonte

Respostas:

1

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:

  1. Crie muitas cópias de um gráfico específico Hn,p .
  2. 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 ).
  3. 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 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 xy é um vetor com n2 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 dexysã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 .

Mikhail Rudoy
fonte