¿Qué separa los problemas globales fáciles de los problemas globales difíciles en los gráficos de ancho de árbol acotado?

Muchos problemas de gráficos duros se pueden resolver en tiempo polinómico en gráficos de ancho de árbol acotado . De hecho, los libros de texto suelen utilizar, por ejemplo, un conjunto independiente como ejemplo, que es un problema local . Aproximadamente, un problema local es un problema cuya solución se puede verificar examinando un pequeño vecindario de cada vértice.

Curiosamente, incluso los problemas (como el camino hamiltoniano) de naturaleza global todavía se pueden resolver de manera eficiente para gráficos de ancho de árbol acotado. Para tales problemas, los algoritmos de programación dinámica habituales deben realizar un seguimiento de todas las formas en que la solución puede atravesar el separador correspondiente de la descomposición del árbol (véase, por ejemplo, [1]). Se proporcionaron algoritmos aleatorios (basados ​​en el llamado corte y conteo) en [1], y se desarrollaron algoritmos mejorados (incluso deterministas) en [2].

No sé si es justo decir eso, pero al menos algunos problemas globales se pueden resolver de manera eficiente para gráficos de ancho de árbol acotado. Entonces, ¿qué pasa con los problemas que siguen siendo difíciles en tales gráficos? Supongo que también son de naturaleza global, pero ¿qué más? ¿Qué separa estos problemas globales difíciles de los problemas globales que se pueden resolver de manera eficiente? Por ejemplo, ¿cómo y por qué los métodos conocidos no podrían proporcionarnos algoritmos eficientes para ellos?

Por ejemplo, uno podría considerar los siguientes problemas:

Extensión precoloring borde Dado un grafo con unos bordes de colores, decidir si este colorante se puede extender a una adecuada -Edge-coloración de la gráfica .k $G$$k$$G$

La extensión de precoloración de bordes (y su variante de color de borde de lista) es NP-complete para gráficos bipartitos en serie-paralelo [3] (tales gráficos tienen un ancho de árbol como máximo 2).

Coloración de borde de suma mínima Dado un gráfico , encuentre una coloración de borde tal que si y tienen un vértice común, entonces . El objetivo es minimizar , la suma de la coloración.χ : E → N e 1 e 2 χ ( e 1 ) ≠ χ ( e 2 ) E ′ χ ( E ) = ∑ e ∈ E χ ( e $G=(V,E)$$\chi : E \to \mathbb{N}$$e_1$$e_2$$\chi(e_1) \neq \chi(e_2)$$E'_\chi(E) = \sum_{e \in E} \chi(e)$

En otras palabras, tenemos que asignar números enteros positivos a los bordes de un gráfico de manera que los bordes adyacentes reciban números enteros diferentes y la suma de los números asignados sea mínima. Este problema es NP-hard para 2-árboles parciales [4] (es decir, gráficos de ancho de árbol como máximo 2).

Otros de estos problemas difíciles incluyen el problema de los caminos de borde disjunto, el problema del isomorfismo del subgrafo y el problema del ancho de banda (ver, por ejemplo, [5] y las referencias allí). Para problemas que siguen siendo difíciles incluso en los árboles, vea esta pregunta .

[1] Cygan, M., Nederlof, J., Pilipczuk, M., van Rooij, JM y Wojtaszczyk, JO (2011, octubre). Resolver problemas de conectividad parametrizados por el ancho del árbol en un tiempo exponencial único. En Fundamentos de Ciencias de la Computación (FOCS), 2011 Simposio Anual IEEE 52 en (pp. 150-159) IEEE

[2] Bodlaender, HL, Cygan, M., Kratsch, S. y Nederlof, J. (2013). Algoritmos determinísticos de tiempo exponencial único para problemas de conectividad parametrizados por ancho de árbol. En autómatas, idiomas y programación (pp. 196-207). Springer Berlin Heidelberg.

[3] Marx, D. (2005). NP-completitud de la lista de colores y extensión de precoloración en los bordes de los gráficos planos. Journal of Graph Theory, 49 (4), 313-324.

[4] Marx, D. (2009). Resultados de complejidad para una coloración de borde de suma mínima. Matemática Aplicada Discreta, 157 (5), 1034-1045.

[5] Nishizeki, T., Vygen, J. y Zhou, X. (2001). El problema de las rutas de disyunción de borde es NP-completo para los gráficos en serie-paralelo. Matemática Aplicada Discreta, 115 (1), 177-186.

La mayoría de los algoritmos para gráficos de ancho de árbol acotado se basan en alguna forma de programación dinámica. Para que estos algoritmos sean eficientes, necesitamos vincular el número de estados en la tabla de programación dinámica: si desea un algoritmo de tiempo polinomial, entonces necesita un número polinómico de estados (por ejemplo, n ^ tw), si desea demuestre que el problema es FPT, generalmente desea mostrar que el número de estados es alguna función del ancho de árbol. El número de estados generalmente corresponde al número de diferentes tipos de soluciones parciales cuando se rompe el gráfico en algún separador pequeño. Por lo tanto, un problema es fácil en los gráficos de ancho de árbol limitado generalmente porque las soluciones parciales que interactúan con el mundo exterior a través de un número limitado de vértices tienen solo un número limitado de tipos. Por ejemplo, en el problema del conjunto independiente, el tipo de solución parcial depende solo de los vértices de límite seleccionados. En el problema del ciclo hamiltoniano, el tipo de solución parcial se describe por la forma en que las subrutas de la solución parcial coinciden entre sí con los vértices del límite. Las variantes del teorema de Courcelle dan condiciones suficientes para que un problema tenga la propiedad de que las soluciones parciales solo tienen un número limitado de tipos.

Si un problema es difícil en los gráficos de ancho de árbol acotado, generalmente se debe a uno de los siguientes tres motivos.

1. Hay interacciones en el problema no capturadas por el gráfico. Por ejemplo, Steiner Forest es NP-hard en gráficos de ancho de árbol 3, intuitivamente porque los pares de origen-destino crean interacciones entre vértices no adyacentes.

Elisabeth Gassner: El problema del bosque Steiner revisitado. J. Algoritmos discretos 8 (2): 154-163 (2010)

MohammadHossein Bateni, Mohammad Taghi Hajiaghayi, Dániel Marx: Esquemas de aproximación para Steiner Forest en gráficos planos y gráficos de ancho de árbol acotado. J. ACM 58 (5): 21 (2011)

2. El problema se define en los bordes del gráfico. Entonces, incluso si una parte del gráfico está unida al resto del gráfico a través de un número limitado de vértices, podría haber muchos bordes incidentes a esos pocos vértices y luego el estado de una solución parcial solo puede describirse describiendo el estado de Todos estos bordes. Esto es lo que dificultó los problemas en [3,4].

3. Cada vértice puede tener una gran cantidad de estados diferentes. Por ejemplo, la cubierta de vértices capacitada es W [1] -paráficamente parametrizada por el ancho del árbol, intuitivamente porque la descripción de una solución parcial implica no solo indicar qué vértices del separador se seleccionaron, sino también cuántas veces cada vértice seleccionado del separador fue Se utiliza para cubrir los bordes.

Michael Dom, Daniel Lokshtanov, Saket Saurabh, Yngve Villanger: Dominación y cobertura capacitadas: una perspectiva parametrizada. IWPEC 2008: 78-90

Mi sugerencia sería mirar cuidadosamente el teorema de Courcelle , que los problemas que se pueden expresar en (ciertas extensiones de) lógica de segundo orden monádica tienen algoritmos FPT cuando se parametrizan por el ancho del árbol. Mi sospecha es que esto cubre muchos o la mayoría de los ejemplos conocidos de problemas de FPT para estos gráficos. Desde este punto de vista, su distinción local / global parece estar estrechamente relacionada con la distinción entre problemas expresables en MSO existenciales frente a problemas que tienen niveles más altos de cuantificación en sus formulaciones de MSO. Para volver a su pregunta real, la falta de una formulación de MSO (que puede probarse incondicionalmente en muchos casos utilizando ideas relacionadas con el teorema de Myhill-Nerode ) sería evidencia de la falta de un algoritmo FPT (más difícil de probar sin supuestos teóricos de complejidad).

Creo que uno de esos ejemplos es el problema de corte más escaso. Uniforme problema más escasa corte es solucionable en los gráficos de ancho de árbol acotada pero ponderado problema más escasa corte no es siquiera approximable (mejor que 17/16) en gráficos de treewidth acotada.

Hay muchas variantes diferentes del problema de corte más disperso, pero una de las más conocidas es la siguiente.

$G=(V,E)$$w:E(G)\rightarrow N$$E(S,V\setminus S) \subseteq E(G)$$S \subset V$$\frac{W(E(S,V\setminus S))}{|S||V\setminus S|}$$E'\subseteq E(G)$$W(E')=\sum_{e\in E'}w(e)$

El ingrediente principal está hecho de dos cosas:

1. Funciones adicionales, como aquí la función de peso. Pero todavía hay algunos problemas con la función de peso que no son muy difíciles en gráficos no dirigidos de ancho de árbol acotado.

2. La naturaleza del problema de corte más escaso. Realmente existe la existencia de más de una dependencia para la programación dinámica en la definición del problema. Intuitivamente, la buena solución es la que dividimos un gráfico (eliminando algunos bordes) en dos tamaños casi iguales, por otro lado, en esta partición eliminamos la menor cantidad de bordes que usamos. La razón por la cual el problema es difícil en el gráfico de ancho de árbol acotado es que debemos aplicar la programación dinámica en dos direcciones, pero ambas direcciones dependen una de la otra.

En general, si el problema es de tal manera que necesita más de una dimensión para la programación dinámica y también esas dimensiones dependen entre sí, entonces el problema tiene el potencial de ser difícil en gráficos de ancho de árbol acotado. Podemos ver este patrón tanto en los problemas de la pregunta como en el problema de corte más escaso. (En el primer problema, queremos mantener el color anterior, por otro lado, mantener el color lo más pequeño posible, en el segundo problema, obviamente, hay dos funciones que dependen unas de otras)