El ancho de árbol juega un papel importante en los algoritmos de FPT, en parte porque muchos problemas están parametrizados por FPT por el ancho de árbol. Una noción relacionada, más restringida, es la de ancho de ruta. Si un gráfico tiene un ancho de ruta , también tiene un ancho de árbol como máximo k , mientras que en la dirección inversa, el ancho de árbol k solo implica un ancho de ruta como máximo k log n y esto es estricto.
Dado lo anterior, uno puede esperar que pueda haber una ventaja algorítmica significativa en los gráficos de ancho de ruta acotado. Sin embargo, parece que la mayoría de los problemas que son FPT para un parámetro son FPT para el otro. Tengo curiosidad por saber de cualquier contraejemplo a esto, es decir, problemas que son "fáciles" para el ancho de ruta pero "difíciles" para el ancho de árbol.
Permítanme mencionar que me sentí motivado a hacer esta pregunta al encontrarme en un artículo reciente de Igor Razgon ("Sobre OBDD para CNF de ancho de árbol limitado", KR'14) que dio un ejemplo de un problema con una solución de cuando k es el ancho de ruta y un límite inferior (aproximadamente) n k cuando k es el ancho del árbol. Me pregunto si existen otros especímenes con este comportamiento.
Resumen: ¿Hay algún ejemplo de problemas naturales que sean W-hard parametrizados por treewidth pero FPT parametrizados por pathwidth? En términos más generales, ¿hay ejemplos de problemas cuya complejidad se sabe / cree que es mucho mejor cuando se parametriza por ancho de ruta en lugar de ancho de árbol?
fuente
Respuestas:
Se muestra que [1] el Problema del Cartero Chino Mixto (MCPP) parametrizado por el ancho de ruta es -duro, incluso si todos los bordes y arcos del gráfico de entrada G tienen peso 1 y es FPT con respecto a la profundidad del árbol. Este es el primer problema que saben que se ha demostrado que es W [W[1] G 1 duro con respecto al ancho del árbol pero FPT con respecto a la profundidad del árbol. Tenga en cuenta que el ancho de ruta de un gráfico se encuentra entre su ancho de árbol y la profundidad del árbol.W[1]
El problema Steiner Multicut, que pide, dado un grafo no dirigido , una colección T = { T 1 , . . . , T t } , T i ⊆ V ( G ) , de conjuntos terminales de tamaño como máximo p , y un número entero k , si hay un conjunto S de como máximo k bordes o nodos de manera que de cada conjunto T i al menos uno par de terminales está en diferentes componentes conectados de G S .G T={T1,...,Tt} Ti⊆V(G) p k S k Ti G S
[1] https://core.ac.uk/download/pdf/77298274.pdf
[2] http://drops.dagstuhl.de/opus/volltexte/2015/4911/pdf/11.pdf
fuente