¿Gráficos planos de 3 colores en

9

Me preguntaba si se sabe que la tarea de buscar colores planos 3 es de complejidad O(cn)o inferior? Parece que sería una consecuencia intuitiva basada en los resultados del separador plano, pero enwikipediasolo menciona conjuntos independientes, árboles Steiner, ciclos hamiltonianos y TSP. A continuación incluyo un razonamiento que creo que casi logra este límite.

Con un diagrama de decisión reducido a cero, (ZDD), creo que puede obtener O(cO(log2(n)n)), y tenía curiosidad por saber cómo podría hacerlo mejor. Lo que se me ocurrió es bastante rudimentario. Nota: en todo momento, el ZDD que describo es ternario, pero no creo que eso importe mucho. Para el ZDD, dado un orden,L={v1vn}, de vértices a color, el número de nodos en el pasoiserá exponencial con respecto al tamaño de la frontera,Fi={vk|k<ivk vj,ji}.

Para crear su orden L , puede crear un árbol óptimo de descomposición de ramas, b , en tiempo polinómico, que tiene un ancho como máximo n . Luego, seleccione una hoja aleatoriavdebpara que sea su raíz. Con un BFS, pondere cada bordeepor el número de hojas no conectadas avsi fuera a eliminaredeb. Luego, haga un DFS para finalmente crearL, siempre bajando por el borde más alejado dev, eligiendo el que tenga menos peso si hay un empate y eligiendo arbitrariamente si todavía hay un empate. Cuando llegamos a una hoja,(u,v)agregueu/vaLsi alguna no está enL. Let ci ser el componente inducida en b por los vértices visitados cuando añadimos vi a L . Entonces, Fi está limitado por el ancho de la rama multiplicado por el número de aristas xi que debe eliminarse de b para obtener el componente ci . x está limitado aproximadamente por log2 de los vértices en b , que es lineal a n ya que estamos tratando con gráficas planas.

Con eso, verifica los tres colores para cada nodo para cada una de las n fronteras y listo.

Zachary Hunter
fuente
1
¿Por qué se rechazó esta pregunta?
Sasho Nikolov
55
No es difícil encontrar un algoritmo DP que se ejecute en para verificar si un gráfico con ancho de árbol k se puede colorear con 3 colores. Como los gráficos planos tienen un ancho de árbol O ( 3kpoly(n)kel límite de tiempo deseado sigue. O(n)
Chandra Chekuri
55
El teorema del separador plano es suficiente para obtener una descomposición del árbol de ancho en tiempo polinomial. No necesita un algoritmo exacto para el tiempo de ejecución reclamado. También hay una aproximación de factor constante para el ancho del árbol en los gráficos planos. Estos son resultados bien conocidos. O(n)
Chandra Chekuri
3
Un comentario menor: desde el n3constO(cn)
1
O(cn)

Respuestas:

8

Recomiendo leer las Secciones 7 y 14 en el excelente libro de Cygan, Fomin, Kowalik, Lokshtanov, Marx, Pilipczuk, Pilipczuk y Saurabh .

3n9n2339n2poly(n)<141n

32Ω(n)3332o(n)

Alex Golovnev
fuente
2
Podemos encontrar la descomposición exacta de las ramas en tiempo polinómico en gráficos planos. Esto es por papel de Seymour y Thomas: enrutamiento de llamadas y el cazador de ratas. Entonces puedes eliminar un factor 3 del exponente.
Saeed
2
n
1
2n