Coloración gráfica aproximada con un límite superior prometido en el conjunto independiente máximo

En mi trabajo surge el siguiente problema:

¿Existe un algoritmo conocido que se aproxime al número cromático de un gráfico sin un conjunto independiente de orden 65? (Por lo tanto, se conoce alfa (G) <= 64 y | V | / 64 es un límite inferior trivial, | V | un límite superior trivial. ¿Pero existen aproximaciones mejor probadas bajo esta condición especial?)

¿Qué pasa si nos relajamos al número cromático fraccional? ¿Y a "buenos" tiempos de ejecución en casos promedio?

ds.algorithms graph-algorithms approximation-algorithms graph-colouring cyrix42
fuente

Creo que esta es una excelente pregunta para este sitio; Esperemos que alguien tenga una buena respuesta.

Jukka Suomela

@TysonWilliams: Creo que la pregunta es perfectamente clara. Olvida el comentario, vuelve a leer la pregunta. :)

Jukka Suomela

Lo curioso es que estas condiciones garantizan que la aproximación trivial sea una aproximación de 64 al óptimo. Me pregunto si solo la promesa de un pequeño número de independencia puede dar un mejor algoritmo.

Sasho Nikolov

¿El problema está motivado por la aplicación práctica? Si es así, uno debería enfocarse en heurísticas interesantes que van a funcionar bien; mejorar la aproximación trivial no es tan interesante.

Chandra Chekuri

O (n^{64})

$O(n^{64})$

Respuestas:

Calcule una coincidencia máxima en el complemento del gráfico de entrada. Cada nodo no coincidente debe estar en una clase de color diferente en cualquier color. Entonces: si obtiene al menos cn bordes coincidentes, entonces la coincidencia misma le da un color con un límite superior de (1-c) n, y una relación de aproximación de 64 (1-c). Si no obtiene al menos cn bordes, entonces obtiene un límite inferior de (1 - 2c) n colores y una relación de aproximación de 1 / (1-2c). Resolver la ecuación 64 (1-c) = 1 / (1-2c) conduce a una relación de aproximación ligeramente mayor que 32; vea el comentario de Sasho Nikolov para el valor exacto.

David Eppstein
fuente

c = 3 / 16 (4 - \sqrt{2}) \approx 0.5

$c = 3/16 (4-\sqrt{2}) \approx 0.5$

\approx 32

$\approx 32$

k

$k$

α (G)

$\alpha(G)$

\frac{k}{2}

$\frac{k}{2}$

k

$k$

$H$ $H$

http://en.wikipedia.org/wiki/Colouring_number#Algorithms

Andrew D. King
fuente

Corrección menor: no es cierto que el número de coloración sea igual al menor número de colores en una coloración codiciosa. Si ordena los vértices de acuerdo con sus colores en una coloración óptima (con la propiedad adicional de que la primera clase de color es máxima y la segunda es máxima en el gráfico restante, etc.), el algoritmo codicioso encontrará la misma coloración óptima.

David Eppstein