Uso de la optimización para colorear o la decisión de coloración para resolver la búsqueda para colorear

Question

¿Cómo puedes mostrar que búsqueda para colorear se puede resolver haciendo un número polinomial de llamadas a la solución para optimización para colorear o decisión para colorear? (Búsqueda para colorear es el algoritmo para colorear los vértices de un gráfico de tal manera que los vértices adyacentes tienen un color diferente).

No estaba seguro de cómo resolverlo, pero esto es lo que intenté (elegí usar optimización para colorear):

Búsqueda para colorear se puede resolver llamando optimización para colorear y encontrar el valor $ m $, que es la cantidad de colores necesarios para que no hay dos vértices adyacentes que tengan el mismo color. Una vez que se encuentra $ m $ búsqueda para colorear puede colorear los vértices del gráfico girando a través de los colores de $ M $ diferentes para cada vértice.

¿Estoy en el camino correcto?

Answer 1

Dado un gráfico $ G $, queremos hacer dos cosas:

1. Encuentra el más pequeño $ k $ tal que $ g $ es $ k $ -colourable,
2. Dado tal $ K $, encuentre una coloración de $ G $ con $ K $ Colors.

Si tenemos un oráculo para la versión de decisión del problema de coloración, podemos hacer ambas cosas.

Para la primera parte podemos realizar una búsqueda para encontrar el óptimo $ K $. Incluso el enfoque ingenuo aquí está bien, podemos preguntar secuencialmente si $ G $ es $ K $ -Colourable por $ K = 1,2, ldots, n $. Luego hacemos como máximo $ N $ llamadas al Oracle. Por supuesto, podemos realizar una búsqueda binaria y reducir esto a $ log n $ llamadas. (Tenga en cuenta que así también es cómo resolvemos la versión de optimización con la versión de decisión).

Luego, dado que hemos resuelto lo que $ K $ es óptimo, podemos encontrar un $ K $-colouring de $ g $ usando el oráculo de decisión. La única arruga es que el Oracle no toma coloraciones parciales, por lo que necesitamos una forma de codificar en el gráfico que un vértice en particular ha sido coloreado de un color particular.

Para hacer esto, realmente usamos el Oracle en un gráfico auxiliar, que llamaremos $ G^{+} $, es decir $ G $ más un $ K_ {K} $ con algunos bordes adicionales. Por supuesto, el $ K_ {K} $ necesita exactamente $ K $ colores, por lo que podemos usar sus vértices para indicar qué colores están disponibles para un vértice. Deje que los vértices $ {k_ {1}, ldots, k_ {k} } $ del $ k_ {k} $ correspondan a los colores $ {c_ {1}, ldots, c_ {k} } ps Entonces indicaremos que un vértice $ V $ en $ g $ no poder estar coloreado con color $ c_ {i} $ haciéndolo adyacente a $ k_ {i} $. Además, si coloreamos un vértice con color $ c_ {j} $ lo haremos adyacente a cada $ k_ {i} $ con $ i neq j $ (y no adyacente a $ k_ {j} $).

Luego hacemos repetidamente lo siguiente:

1. Elija un vértice 'sin cojear' $ V in v (g) $.
2. Por cada vértice $ u in n (v) $, si $ u $ ha sido coloreado, entonces hay un $ k_ {i} $ tal que $ uk_ {i} noin e (g) $. Agregue el borde $ vk_ {i} $ a $ e $.
3. Para los vértices restantes $ k_ {j} $ tal que $ vk_ {j} $ aún no está en $ e $, agregamos todo otro Bordes entre $ V $ y el $ K_ {K} $ y pregunte al Oracle si el nuevo gráfico es $ K $ -Colourable. Si es así, mantenemos este gráfico y pasamos al siguiente vértice, si la respuesta es no, deshacemos el paso 3 e intentamos con el siguiente $ k_ {j} $.

Tenga en cuenta que como $ G $ es $ K $ -Colourable, hay unos $ k_ {j} $ con el que funcionará el paso tres. Luego, cuando hemos procesado cada vértice, cada vértice en $ g $ es no Adyacente a exactamente un vértice en $ k_ {k} $, esto indica con qué color se puede colorear el vértice para obtener el color. Desde el paso 2, vemos que este no puede ser del mismo color que cualquiera de sus vecinos.

En el paso tres hacemos como máximo las llamadas de $ K $ al Oracle, y lo hacemos para cada vértice en $ G $, por lo que en total hacemos como máximo $ (K+1) n $ llamadas al Oracle (incluida la búsqueda por $ k $).