El número aproximado de coloraciones parece ser fácil en gráficos con exclusión menor utilizando el algoritmo de Jung / Shah. ¿Cuáles son otros ejemplos de problemas que son difíciles en gráficos generales pero fáciles en gráficos excluidos menores?
Actualización 10/24 Parece seguir los resultados de Grohe de que la fórmula que es FPT para probar en gráficos de ancho de árbol limitado es FPT para probar en gráficos excluidos menores. Ahora la pregunta es: ¿cómo se relaciona con la posibilidad de contar las tareas satisfactorias de tal fórmula?
La declaración anterior es falsa. MSOL es FPT en gráficos de ancho de árbol acotado, sin embargo, la capacidad de 3 coloraciones es NP completa en gráficos planos que están excluidos de manera menor.
fuente
Una propiedad interesante de las familias de gráficos cerrados menores es que tienen degeneración limitada . Esto significa que todos los problemas que son fáciles en los gráficos de degeneración limitada son fáciles en los gráficos de una familia cerrada menor.
Entonces, por ejemplo, encontrar si un gráfico contiene una camarilla de tamaño k suele ser un problema difícil y los mejores algoritmos son como . Sin embargo, si sabemos que la degeneración es una constante, entonces las k-camarillas se pueden encontrar en el tiempo lineal, es decir, el tiempo O (n). El artículo de Wikipedia sobre el problema de la camarilla también proporciona información sobre esto. (El tiempo de ejecución preciso es algo así como O ( k d ( G ) k n )) . Este algoritmo es de Chiba y Nishizeki .O(nk) O(kd(G)kn)
Se pueden encontrar otros ejemplos en esta respuesta de David Eppstein en MathOverflow a una pregunta similar sobre gráficos con degeneración limitada.
fuente
Como complemento, otra propiedad útil para los algoritmos en gráficos excluidos menores es que estos gráficos tienen separadores pequeños . Más precisamente, debido a
hay un algoritmo de tiempo lineal para encontrar un separador de tamaño , o un O ( n 3 / 2 + m ) algoritmo de tiempo para encontrar un separador de tamaño O ( n 1 / 2 ) .O(n2/3) O(n3/2+m) O(n1/2)
Los separadores son buenos para las técnicas de programación dinámica , y muchos problemas de NP completo muestran algoritmos rápidos con una buena relación de aproximación, digamos que la solución está dentro de un factor constante del óptimo, o incluso un PTAS. Las gráficas planas y, en general, las gráficas de género acotadas son buenos puntos de partida cuando se intenta resolver problemas en gráficas excluidas menores.
fuente
Este artículo ofrece una versión algorítmica de una cierta descomposición (algo compleja de explicar) para gráficos menores excluidos garantizados por el teorema de Robertson y Seymour, que arroja varios de estos resultados de aproximación mejorados. También revise las referencias allí.
fuente
La conjetura de Hadwiger afirma que cadaKt (t−1) Kt (t−1) t−2
fuente