A coloração do gráfico 3 é auto-redutível

Estou interessado na auto-redutibilidade do problema do Graph 3-Coloralibity.

Definição do problema do gráfico 3-Coloralibity.

Dado um gráfico não direcionado $G$ existe uma maneira de colorir os nós vermelho, verde e azul para que nenhum nó adjacente tenha a mesma cor?

Definição de auto-redutibilidade.

Uma linguagem $L$ é auto-redutível se uma máquina Oracle Turing Machine $T$ existe tal que $L=L(T^L)$ e para qualquer entrada $x$ de comprimento $n$ , $T^L(x)$ consulta o oráculo por palavras de comprimento, no máximo $n-1$ .

Gostaria de mostrar de maneira muito estrita e formal que a coloração do gráfico 3 é auto-redutível.

A prova de auto-redutibilidade do SAT pode ser usada como exemplo ( auto-redutibilidade do SAT ).

Na minha opinião, a idéia geral de prova de auto-redutibilidade do gráfico 3-colorability é diferente da prova de auto-redutibilidade SAT em alguns aspectos.

O SAT tem duas opções para cada literal (verdadeiro ou falso) e o gráfico 3-colorability tem três opções (a saber, vermelho verde azul).
As opções do literal SAT são independentes entre si e as opções de cores do gráfico 3 são estritamente dependentes; qualquer nó adjacente deve ter uma cor diferente; essa propriedade pode ajudar a reduzir a iteração entre todas as cores.

A ideia geral de prova .

Vamos denotar por $c_{v_i}$ a cor do vértice $v_i$ , que pode assumir um dos seguintes valores (vermelho, verde, azul). Definir gráfico $G'$ de um dado gráfico $G$ colorindo o vértice arbitrário $v_0$ atribuir $c_{v_0}$ para 'vermelho' e coloque o gráfico $G'$ com vértice colorido $v_0$ para a entrada do oráculo. Se o oracle responder 1, o que significa que o gráfico modificado ainda é de três cores, salve as atribuições atuais e inicie uma nova iteração, com o vértice diferente $v_1$ escolhido arbitrariamente, vértice colorido $v_1$ de acordo com as cores dos vértices adjacentes. se o oracle responder 0, o que significa que a tarefa anterior quebrou três cores, escolha uma cor diferente do conjunto de três cores, mas ainda de acordo com as cores dos vértices adjacentes.

A prova anterior não é robusta em matemática, a questão é como melhorá-la e torná-la mais formal e matemática rigorosa. Parece que preciso distinguir com mais cuidado os casos em que o novo vértice não possui arestas com vértices já coloridos e quando o novo vértice é adjacente aos vértices já coloridos.

Além disso, gostaria de provar que a coloração do gráfico 3 é auto-redutível em baixa.

Definição de linguagem auto-redutível para baixo.

O idioma $A$ é dito ser auto-redutível para baixo se for possível determinar em tempo polinomial se $x \in A$ usando os resultados das consultas mais curtas.

A idéia parece simples e intuitiva: comece colorindo um vértice arbitrário e, em cada iteração, adicione mais um vértice colorido e verifique pelo oracle se o gráfico ainda é de três cores, se não inverter a coloração anterior e verifique outra cor.

Mas como escrever a prova de maneira estrita e mais importante como encontrar uma codificação apropriada de um gráfico.

Em resumo, gostaria de mostrar que a coloração do gráfico 3 é auto-redutível e auto-redutível em sentido estrito e formal.

Eu aprecio compartilhar seus pensamentos conosco.

Atualizar:

auto-redutibilidade descendente

A auto-redutibilidade descendente é aplicada ao problema de decisão e o oracle responde ao mesmo problema de decisão com menos tempo de entrada. No final do processo de auto-redução descendente, devemos ter as atribuições de cores corretas.

A cada 3 - gráfico colorido $G$ com mais de três vértices, tem dois vértices $x,y$ com a mesma cor. Aparentemente, existem apenas três cores e mais de três vértices, portanto, um número de vértices não adjacentes pode ter a mesma cor. Se fundirmos $x$ e $y$ com a mesma cor do resultado, ainda temos um gráfico de 3 cores, apenas porque, se o gráfico é de 3 cores, existe a atribuição correta de todos os vértices adjacentes a $x$ e $y$ de acordo com a mesma cor de $x, y$ , mesclando $x, y$ não precisamos alterar nenhuma cor de nenhum vértice, precisamos apenas adicionar mais arestas entre os vértices já corretamente coloridos (sei que não é a melhor explicação, aprecio se alguém puder explicar melhor). Em cada iteração, pegamos dois vértices não adjacentes $x,y$ do gráfico $G$ mesclar $x$ e $y$ e obter gráfico $G'$ qual é a nossa entrada mais curta para o oráculo. A Oracle responde se é de três cores ou não. Agora o problema está antes de configurar $G'$ na entrada do oracle eu devo colorir o vértice mesclado e testar a colorabilidade de $G'$ , se não for de três cores, altere a cor, mas como implementá-la corretamente, preciso da codificação correta.

auto-redutibilidade

Primeiro, devemos verificar se um determinado gráfico $G$ é de 3 cores, então defina-o na entrada do oracle, e o oracle responderá se for de 3 cores, se sim, inicie o processo. Quaisquer dois vértices não adjacentes podem ter a mesma cor no gráfico de três cores. O processo de auto-redutibilidade que devemos executar em iterações, acho que podemos começar com um pequeno subgrafo $G'$ de um dado gráfico $G$ e em cada iteração adicione mais um vértice de $G$ para $G'$ . Em paralelo, devemos manter a atribuição de vértices já coloridos. Infelizmente, ainda não entendi completamente a idéia. Gostaria de receber ajuda e dicas.

complexity-theory reductions com
fonte

apenas uma observação: acho que na auto-redução você deve usar a versão "nua" do problema de decisão: a entrada do problema de decisão é um gráfico e não um gráfico com alguns nós coloridos. Portanto, você deve modificar o gráfico original para simular uma coloração forçada de alguns nós (e tentar manter a instância mais curta). No SAT, isso é mais fácil porque você apenas define o valor de uma variável e simplifica as cláusulas.

Vor

Qual é a diferença entre auto-redutibilidade e auto-redutibilidade descendente?

Yuval Filmus

@YuvalFilmus, set

S

$S$ é auto-redutível para baixo se houver uma redução de Cook de

S

$S$ que faz consultas cada uma mais curtas que a entrada da redução (na entrada

x

$x$ a redução faz a consulta

q

$q$ então

| q | < | x |

$|q| < |x|$ )

com

Considerando que um conjunto é auto-redutível se ...?

Yuval Filmus

O problema de pesquisa de qualquer relação

R

$R$ é chamado de auto-redutível se puder ser reduzido ao problema de decisão de

S_{R}

$S_R$ .

com

Respostas:

Como Vor menciona em seu comentário, sua redução não funciona, pois a 3 cores não aceita atribuições parciais de cores. O problema é ainda mais profundo, uma vez definindo a cor de um único vértice não faz qualquer progresso para determinar se o gráfico é de 3 colorable: na verdade, o gráfico é 3-colorable sse há uma 3-coloração em que vértice $v$ é atribuído cor $c$ , para qualquer $v,c$ você escolhe.

Aqui está uma dica sobre como resolver seu exercício, segunda parte. Em qualquer coloração 3 de um gráfico $G$ em mais de três vértices, existem dois vértices $x,y$ ficando da mesma cor (por quê?). Se fundirmos $x$ e $y$ , o gráfico resultante ainda é de três cores (por quê?). Tente usar essa idéia para construir um algoritmo de redução automática para 3 cores.

Edit: E aqui está uma dica sobre como resolver o exercício, primeira parte. Considere dois vértices não conectados $x,y$ . Se houver uma coloração na qual eles tenham a mesma cor, então $G_{xy}$ é de 3 cores (por quê?) e uma coloração de $G$ pode ser extraído de uma coloração de $G_{xy}$ (como?). Quando esse processo será interrompido?

Yuval Filmus
fonte

Pontos extras se você puder encontrar uma redução que chama o oráculo

O (1)

$O(1)$ vezes.

Yuval Filmus

Muito obrigado pela dica, em vez de colorir parcialmente, podemos usar o gráfico auxiliar

G^{'}

$G'$ e estendê-lo de acordo com

G

$G$ . Gráfico

G

$G$ com mais de três vértices tem dois vértices

x, y

$x, y$ com a mesma cor, apenas porque a Oracle respondeu que é de três cores (mas os vértices são mais de três), então deve haver vértices da mesma cor. Mas não entendo por que o gráfico ainda é de três cores quando mesclamos dois vértices com a mesma cor. Por outro lado, por que precisamos adicionar arestas entre os vértices já coloridos.

com

De acordo com o número de chamadas. Em geral, podemos atribuir a mesma cor a todos os vértices não adjacentes; portanto, neste caso, não precisamos pedir ao oracle em todas as atribuições (por outro lado, há três cores, e é crucial assumir a atribuição correta. Tarefa aparentemente correta em

G^{'}

$G'$ , pode se tornar falso em

G

$G$ )

29/12

Suponha que um gráfico

G

$G$ tem um 3-coloração

c

$c$ de tal modo que

c (x) = c (y)

$c(x) = c(y)$ . Agora considere o gráfico

G_{x y}

$G_{xy}$ obtido por fusão

x

$x$ e

y

$y$ . Você pode encontrar um 3-coloração para

G_{x y}

$G_{xy}$ ? E o inverso?

Yuval Filmus

Agora que compreendo a diferença entre auto-redutibilidade e auto-redutibilidade descendente, percebo que minha sugestão só faz sentido para a última. Adicionada uma dica diferente para a primeira. Talvez isso ajude.

Yuval Filmus

Talvez assim. Podemos adicionar dois vértices l1 e l2 conectados. Primeiro, nós os conectamos com qualquer vértice v *. Observe que esse comportamento significa que, finalmente, apenas bloqueamos alguns vértices de cores, incluindo v *.

Em seguida, executamos a versão de decisão do 3-colorability, se o algoritmo de decisão aceitar, adicionamos esse vértice em s_1. repetimos esta etapa com todos os vértices (conecte l1 e l2 com outro vértice), descobriremos que, finalmente, são encontrados todos os vértices da mesma cor (denotados por vermelho) e esses vértices com a cor vermelha denotados por s_1.

Se houver algum problema, aponte.🤥

Em seguida, exatamente como fizemos acima, adicione outros dois vértices conectados (l3 l4). Primeiro, nós os conectamos a qualquer vértice, exceto aqueles em s_1, execute o algoritmo de decisão. Então outro.....

YK X
fonte