¿Qué es fácil para los gráficos excluidos menores?

31

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.

Yaroslav Bulatov
fuente

Respuestas:

23

El resultado más general conocido es el de Grohe. Se presentó un resumen en julio de 2010:

  • Martin Grohe, Definabilidad de punto fijo y tiempo polinómico en gráficos con menores excluidos , LICS 2010. ( PDF )

En resumen, cualquier enunciado que sea expresable en lógica de punto fijo con conteo tiene un algoritmo de tiempo polinómico en clases de gráficos con al menos un menor excluido. (FP + C es lógica de primer orden aumentada con un operador de punto fijo y un predicado que da la cardinalidad de conjuntos de vértices definibles). La idea clave es que excluir a un menor permite que las gráficas de la clase tengan descomposiciones arboladas ordenadas que son definibles en la lógica de punto fijo (sin contar).

Por lo tanto, se puede obtener una gran clase de respuestas a su pregunta considerando propiedades que se pueden definir en FP + C pero que son difíciles de contar.


Editar: no estoy seguro de que esto realmente responda su pregunta, y menos aún para su actualización. El puntero y la declaración del resultado de Grohe son correctos, pero no creo que el texto tachado sea relevante para su pregunta. (Gracias a Stephan Kreutzer por señalar esto). Podría valer la pena aclarar: ¿desea un problema de conteo que sea difícil en general pero fácil en las clases excluidas menores, o un problema de decisión?

András Salamon
fuente
1
Interesante ... Me pregunto cómo será esta descomposición en forma de árbol para los gráficos planos
Yaroslav Bulatov
2
Un teorema útil que encontré es que la propiedad es expresable en FP + C si es decidible en tiempo polinómico en un gráfico tw acotado. Ahora la pregunta es: ¿cómo se relaciona la complejidad de los problemas de decisión de FP + C con la complejidad de los problemas de conteo análogos?
Yaroslav Bulatov
@Yaroslav: ¿Podría dar una referencia para esto una vez que esté escrito? Gracias.
gphilip
3
Lol, en realidad no lo descubrí, lo "encontré" en la página 2 de "Lógica, gráficos y algoritmos" de Grohe
Yaroslav Bulatov
18

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.

Robin Kothari
fuente
55
Mi artículo arxiv.org/abs/1006.5440 tiene algunos resultados más recientes sobre la inclusión de camarillas con baja degeneración, incluido el tiempo de ejecución algo mejor ( d n 3 d / 3 ) para enumerar todas las camarillas máximas. O(dn3d/3)
David Eppstein
No puedo ver qué relación hay entre los gráficos de menor cerrado (su respuesta) y los de menor exclusión (pregunta). También el conjunto de todos los gráficos completos es menor cerrado, pero no son de degeneración limitada.
Saeed
Menor cerrado = menor excluido. Todas las familias no triviales de gráficos cerrados menores tienen degeneración limitada. Debería haber agregado "no trivial" a mi declaración original.
Robin Kothari
En primer lugar menor cerrada! = Menor excluidos (en vez excluidos menor menor cerrada), de lo contrario se puede proporcionar muchos nuevos algoritmos de aproximación y parametrizados para muchos clase densa de gráficos. Además, ¿qué son los gráficos cerrados menores no triviales? por ejemplo, los gráficos de ancho de árbol como máximo f (| G |) son triviales o no triviales? o clase de gráficos densos (que son menores cerrados y bien ordenados), ¿son triviales menores cerrados o no triviales? Su definición no está clara, y el lector no puede adivinar lo que piensa (y algunas partes de sus definiciones son incorrectas, como dije al comienzo).
Saeed
Puedo decirte lo que quiero decir con una familia gráfica cerrada menor. es un menor de G si H se puede obtener de G eliminando bordes, eliminando vértices aislados o contrayendo bordes. Una familia de gráficos es un conjunto de gráficos F sin etiquetar no dirigidos (generalmente un conjunto infinito). F es una familia de menor importancia-cerrado si para todo G en F , todos los menores de G también están en F . Una familia no es trivial si no es el conjunto de todos los gráficos. Los gráficos de ancho de árbol k (para k constante ) son de menor importancia pero los gráficos de ancho de árbol f ( | GHGHGFFGFGFkk no son en general menores cerrados. Así es como lo entiendo. Podría estar equivocado, por supuesto. f(|G|)
Robin Kothari
15

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

Un algoritmo de tiempo lineal para encontrar un separador en un gráfico que excluya a un menor , Bruce Reed y David R. Wood, ACM Transactions on Algorithms, 2009,

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.

Hsien-Chih Chang 張顯 之
fuente
¿Alguna idea de si los separadores ayudan a contar el número de colorantes adecuados?
Yaroslav Bulatov
1
en realidad no, tal vez el documento mencionado por Ian ayuda mejor. Una extensión del resultado se encuentra en "Algoritmos de aproximación mediante descomposición de contracción" por los mismos autores en SODA '07.
Hsien-Chih Chang 張顯 之
15

O(1)

Teoría menor del gráfico algorítmico: descomposición, aproximación y coloración de Demaine, Hajiaghayi y Kawarabayashi

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í.

Ian
fuente
Gracias, eso es bastante fascinante ... Encontré una descripción más accesible del algoritmo de descomposición en "Lógica, gráficos y algoritmos" de Grohe
Yaroslav Bulatov
0

K5K3,3

HH

La conjetura de Hadwiger afirma que cada Kt(t1)Kt(t1)t2

Rupei Xu
fuente