k-Coloring es más rápido que calcular el número cromático
k-Coloring is Faster than Computing the Chromatic Number
Un nuevo algoritmo aleatorio resuelve el k-coloreo de grafos con n vértices en tiempo (2−ε_k)^n, donde ε_k>0 para cada k fijo. Anteriormente, solo se conocían soluciones más rápidas para k≤6. El resultado generaliza y combina herramientas de la reducción de (k+2)-coloreo a k-list-coloreo de Zamir (ICALP 2021) y el enfoque basado en contenedores de hipergrafos de Zamir (STOC 2023), junto con nuevos algoritmos para instancias de list-coloreo que mezclan listas largas y cortas. Esto produce una reducción iterable de (k+1)-list-coloreo a k-list-coloreo sobre paletas fijas.
Demostramos que el k-coloreo en grafos de n vértices tiene un algoritmo aleatorio que se ejecuta en tiempo (2−ε_k)^n, donde ε_k>0 para cada k fijo.
- emil-lp
Para los que no estén familiarizados:
K-Coloring es la propiedad de que un grafo puede colorearse con k colores de modo que dos nodos adyacentes no reciban el mismo color. El problema de K-Coloring es un problema de decisión, es decir, una pregunta de sí/no.
El número cromático de un grafo es el menor k para el cual tiene un k-coloreo.
Claramente, si tienes un algoritmo para uno, tienes un algoritmo para el otro.
La pregunta era: ¿es más rápido calcular el k-coloreo que calcular su k mínimo (real), es decir, su número cromático?
Los bosques, los árboles y los grafos bipartitos son 2-coloreables. Los grafos planares son 4-coloreables. Es NP-completo comprobar si el número cromático de un grafo planar es 3.
Hay un problema abierto muy interesante, la conjetura de Hadwiger, que esencialmente dice que el número cromático es el número de clique (menor) (lo que sea que eso signifique).
- black_knight
Al final del artículo de brev hay una sección sobre el uso de LLM.
Ahora, este artículo pasará por revisión por pares. Y así, cuando se publique, confiaremos en el resultado tanto como en cualquier otro resultado publicado en matemáticas. Sin embargo, aunque los humanos no son infalibles, los LLM tienden a escupir contenido seguro que parece correcto. Así que me preocupa cuando se usa de esta manera para producir pruebas. La revisión por pares no es perfecta, y puede que no esté ajustada para detectar el estilo de errores de los LLM.
Hay una solución para esto, que es formalizar el resultado y hacer que sea verificado por máquina. Y con los LLM, me atrevería a decir que esto va a ser la mejor práctica de cara al futuro.
- drivebyhooting
No mucho más rápido.
Cualquier algoritmo de k-coloreo de complejidad F(n) se puede usar para crear un algoritmo de número cromático de complejidad lg(N)F(N) simplemente bisecando en N.