El gráfico de 3 coliabilidad es autoducible

Question

Estoy interesado en la auto-reducibilidad del problema gráfico de 3 colores.

Definición de problema de gráfico 3-coloralización.

Dado un gráfico no dirigido $ G $, ¿existe una forma de colorear los nodos rojos, verdes y azules para que no hay nodos adyacentes que tengan el mismo color?

Definición de autocrucibilidad.

Un idioma $ l $ es autoducible si una máquina oracle turing tm $ t $ existe de tal manera que $ l = l (t^l) $ y por cualquier entrada $ x $ de longitud $ n $, $ t^l (x ) $ consulta el oráculo para palabras de longitud como máximo $ n-1 $.

Me gustaría demostrar de manera muy estricta y formal que el gráfico de 3 Colorabilidad es autoducible.

La prueba de auto-reducibilidad de SAT se puede usar como ejemplo (Autoducibilidad de SAT).

En mi opinión, la idea general de la prueba de autocrucibilidad de la gráfica 3 colorabilidad es diferente de la prueba de la autoleducibilidad SAT en pocos aspectos.

• SAT tiene dos opciones para cada literal (verdadero o falso) y el gráfico de 3 colores tiene tres opciones (es decir, azul verde rojo).
• Las opciones de SAT literal son independientes entre sí y las opciones de colores de la colorabilidad gráfica 3 dependen estrictamente, cualquier nodo adyacente debe tener un color diferente, esta propiedad podría ayudar a hacer menos iteración entre todos los colores.

La idea general de la prueba.

Denotemos por $ c_ {v_i} $ el color del vértice $ v_i $, que puede tomar uno de los siguientes valores (rojo, verde, azul). Define gráfico $ g '$ de un gráfico determinado $ g $ coloreando el vértice arbitrario $ v_0 $, asigne $ c_ {v_0} $ a' rojo 'y coloque el gráfico $ g' $ con vértice coloreado $ v_0 $ a la entrada del oráculo. Si Oracle responde 1, lo que significa que el gráfico modificado aún es 3 colores, guarde las tareas actuales y comience una nueva iteración, con el Vértice diferente $ V_1 $ elegido arbitramente, Color Vertex $ V_1 $ según los colores de los vértices adyacentes. Si Oracle responde 0, lo que significa que la tarea anterior ha roto 3 colorabilidad, elija un color diferente del conjunto de tres colores, pero aún así según los colores de los vértices adyacentes.

La prueba anterior no es matemática robusta, la pregunta es cómo mejorarla y hacerlo más formal y matemático estricto. Parece que necesito distinguir más cuidadosamente los casos cuando el nuevo vértice no tiene ningún bordes con vértices ya coloreados y cuando el nuevo vértice está adyacente a los vértices ya coloreados.

Además, me gustaría demostrar que el gráfico 3 colorabilidad es autoducible hacia abajo.

Definición de lenguaje autocreducible descendente.

Se dice que el lenguaje $ a $ es autoducible a la baja si es posible determinar en tiempo polinomial si $ x en $ utilizando los resultados de consultas más cortas.

La idea parece ser simple e intuitiva: comience con colorear un vértice arbitrario, y en cada iteración agregue un vértice de color más y verifique por Oracle si el gráfico aún es 3 colores, si no revuelve la coloración anterior y verifique otro color.

Pero cómo escribir la prueba de manera estricta y más importante cómo encontrar una codificación apropiada de un gráfico.

En resumen, me gustaría demostrar que el gráfico de 3 colores es autoducible y descendente autoducible de manera estricta y formal.

Apreciaré compartir sus pensamientos con nosotros.

Actualizar:

Autoducibilidad descendente

La auto-reducibilidad descendente se aplica al problema de decisión y su Oracle responde el mismo problema de decisión con una entrada más corta, al final del proceso de auto reducción a la baja, deberíamos tener las tareas de color correctas.

Cada 3 - gráfico colorable $ g $ con más de tres vértices, tiene dos vértices $ x, y $ con el mismo color. Aparentemente, solo hay tres colores y más de tres vértices, por lo que un número de vértices no adyacentes puede tener el mismo color. Si fusionamos $ x $ y $ y $ con el mismo color que el resultado, todavía tenemos 3 gráficos colorables, solo porque, si el gráfico es 3 - colorable, entonces existe la asignación correcta de todos los vértices que están adyacentes a $ X $ y $ y $ de acuerdo con el mismo color de $ x, y $, por lo que al fusionar $ x, y $ no necesitamos cambiar ningún color de ningún vértices, solo necesitamos agregar más bordes entre vértices de colores correctos (Sé que no es la mejor explicación, apreciaré si alguien podría explicarlo mejor). En cada iteración, tomamos dos vértices no adyacentes $ x, y $ de gráfico $ g $, fusionan $ x $ y $ y $ y obtenga gráfico $ g '$, que es nuestra entrada más corta al oráculo. Oracle responde si es de 3 colores o no. Ahora el problema es antes de configurar $ G '$ en la entrada de Oracle, debo colorear el vértice fusionado y la colorabilidad de la prueba de $ g' $, si no es 3 colores, cambia el color, pero cómo implementarlo correctamente, necesito bien codificando para ello.

autocrucibilidad

Primero, debemos verificar si un gráfico determinado $ G $ es de 3 colores, así que configúrelo en la entrada de Oracle, y Oracle responderá si es 3 - colorable, si es así, comience el proceso. Cualquiera de los dos vértices no adyacentes puede tener el mismo color en un gráfico de 3 colores. El proceso de auto-reducibilidad que debemos ejecutar en iteraciones, creo que podemos comenzar desde una pequeña subgraph $ G '$ de un gráfico determinado $ G $ y en cada iteración agregue uno más de $ G $ a $ G' $. En Paralel, debemos mantener la asignación de vértices ya coloreados. Desafortunadamente, todavía no tengo la idea por completo. Agradecería por ayuda y sugerencias.

Answer 1

Como Vor menciona en su comentario, su reducción no funciona, ya que 3 Colorabilidad no acepta tareas parciales de colores. El problema es aún más profundo, ya que establecer el color de un solo vértice no hace ningún progreso en la determinación de si el gráfico es de 3 colores: de hecho, el gráfico es de 3 colores IFF, hay un color de 3 colores en el que el vértice $ V $ se asigna un color $ C $, por cualquier $ V, C $ que elija.

Aquí hay una pista sobre cómo resolver su ejercicio, segunda parte. En cualquier 3 colores de un gráfico $ G $ en más de tres vértices, hay dos vértices $ x, y $ obteniendo el mismo color (¿por qué?). Si fusionamos $ x $ y $ y $, el gráfico resultante sigue siendo 3 colores (¿por qué?). Trate de usar esta idea para construir un algoritmo de autodeducir hacia abajo para 3ulerabilidad.

EDITAR: Y aquí hay una pista sobre cómo resolver el ejercicio, primera parte. Considere cualquier dos vértices no conectados $ x, y $. Si hay un color en el que obtienen el mismo color, entonces $ g_ {xy} $ es 3 colorable (¿por qué?), Y se puede extraer una coloración de $ g $ de una coloración de $ g_ {xy} $ (cómo ?). ¿Cuándo se detendrá este proceso?