Me preguntaba si se sabe que la tarea de buscar colores planos 3 es de complejidad 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 , 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,, de vértices a color, el número de nodos en el pasoserá exponencial con respecto al tamaño de la frontera,.
Para crear su orden , puede crear un árbol óptimo de descomposición de ramas, , en tiempo polinómico, que tiene un ancho como máximo . Luego, seleccione una hoja aleatoriadepara que sea su raíz. Con un BFS, pondere cada bordepor el número de hojas no conectadas asi fuera a eliminarde. Luego, haga un DFS para finalmente crear, siempre bajando por el borde más alejado de, eligiendo el que tenga menos peso si hay un empate y eligiendo arbitrariamente si todavía hay un empate. Cuando llegamos a una hoja,agregue/asi alguna no está en. Let ser el componente inducida en por los vértices visitados cuando añadimos a . Entonces, está limitado por el ancho de la rama multiplicado por el número de aristas que debe eliminarse de para obtener el componente . está limitado aproximadamente por de los vértices en , que es lineal a ya que estamos tratando con gráficas planas.
Con eso, verifica los tres colores para cada nodo para cada una de las fronteras y listo.
fuente
Respuestas:
Recomiendo leer las Secciones 7 y 14 en el excelente libro de Cygan, Fomin, Kowalik, Lokshtanov, Marx, Pilipczuk, Pilipczuk y Saurabh .
fuente