Algoritmos exactos para el conjunto r-dominador en gráficos de ancho de árbol acotado

Dado un grafo, $G = (V, E)$ , quiero encontrar un óptimo -domination para . Es decir, quiero un subconjunto de tal que todos los vértices en$r$$G$$S$$V$$G$ están a una distancia de como máximo $r$ de algún vértice en $S$ , mientras se minimiza el tamaño de $S$ .

De lo que he verificado hasta ahora, obtuve lo siguiente: Existe este problema relacionado de encontrar un centro $(k,r)$ en un gráfico que es un subconjunto $S$ de tamaño como máximo $k$ modo que todos los vértices en el gráfico son a una distancia de casi $r$ de algún vértice en $S$ (aquí, ambos $|S| \leq k$ y $r$ son partes de la entrada) para lo cual Demaine et al . tener un algoritmo FPT para gráficos planos. De lo contrario, el problema es $W[2]$ -duro incluso para $r = 1$ .

¿Se sabe algo sobre la complejidad exacta del problema de dominación para gráficos de ancho de árbol acotado o incluso solo para árboles? (¿Es definible MSO de dominación r ? El problema habitual del conjunto de dominios k es definible por MSO, lo que permitiría utilizar el teorema de Courcelle para concluir que existe un algoritmo de tiempo lineal para el problema). ¿Se conocen resultados de dureza condicional con respecto a este problema?$r$$r$$k$

An (óptimo) -domination para G es un (óptimo) dominación para la r ésima potencia G r y viceversa ( G r se obtiene de G mediante la adición de nuevos bordes entre vértices distintos de distancia como máximo r ).$r$$G$$r$$G^r$$G^r$$G$$r$

Los siguientes hechos son bien conocidos: (1) Todos los poderes de un gráfico fuertemente cordal son fuertemente cordales (A. Lubiw, tesis de maestría; ver también Dahlhaus & Duchet, en gráficos fuertemente cordales, Ars Combin. 24 B (1987) 23-30 ), y (2) La dominación se puede resolver en tiempo lineal para gráficos fuertemente cordales (M. Farber. Dominación, dominación independiente y dualidad en gráficos fuertemente cordales, Discrete Appl. Math., 7 (1984) 115-130). Por lo tanto, la dominación se puede resolver en tiempo polinómico para gráficos fuertemente cordales, en particular para árboles ( r fijos o no).$r$$r$

Gurski y Wanke probaron en este documento que la clique-anchura de es a lo sumo 2 ⋅ ( r + 1 ) tw ( G ) + 1 - 2 , donde tw ( G ) es el árbol de ancho de G . Por lo tanto, para r fijo , las potencias r de los gráficos de ancho de árbol acotado tienen un ancho de camarilla acotado. Por lo tanto, para r fijo , r -domination se puede resolver en tiempo polinómico para gráficos de ancho de árbol acotado (por el teorema de Courcelle). $G^r$$2\cdot (r+1)^{\text{tw}(G)+1}−2$$\text{tw}(G)$$G$$r$$r$$r$$r$

Es bastante fácil hacer programación dinámica en gráficos de ancho de árbol para este problema. Se puede mantener para cada vértice en una bolsa la distancia más corta a algún vértice en la solución parcial y la distancia a la solución futura necesaria para dominar los vértices no dominados.$k$

En total, esto da un tamaño de tabla de por lo que para r solucionado este problema está parametrizado por FPT por el ancho del árbol, sin embargo, si r no se arregla, se convierte en un algoritmo XP. Hasta donde sé, la pregunta de si este problema es FPT para todos los valores de r está abierta.$O(r^k)$$r$$r$$r$

Dawar y Kreutzer han demostrado que el problema es manejable con parámetros fijos en clases de gráficas densas en ninguna parte, que incluye las gráficas planas, las gráficas de ancho de árbol acotado (local) y todas las clases con menores excluidos (localmente).

Dvorak ha demostrado que existe una aproximación de factor de tiempo polinómico constante para las clases de expansión acotada, que incluye los gráficos planos, los gráficos del ancho del árbol acotado y todas las clases con menores excluidos.

Hay un artículo reciente de Glencora Borradaile, Hung Le: Optimal Dynamic Programme for r-Domination Problems over Tree Decompositions (IPEC 2016). Aquí muestran que hay un algoritmo que da como entrada un gráfico , un entero r , y una descomposición de árbol de G de ancho w , calcula un conjunto óptimo de G que domina r en el tiempo O ( ( 2 r + 1 ) w n ) . Además, muestran que esto es lo mejor que se puede hacer, en el siguiente sentido: un algoritmo con tiempo de ejecución O ( ( $G$$r$$G$$w$$r$$G$$O((2r+1)^wn)$ para ϵ > 0 contradeciría la hipótesis del tiempo exponencial fuerte.$O((2r+1-\epsilon)^wn^{O(1)})$$\epsilon > 0$

Slater debe un algoritmo secuencial lineal para calcular una dominación r óptima para un árbol:

P. Slater. Dominación R en gráficos. J. ACM, 23 (3): 446–450, julio de 1976. doi: 10.1145 / 321958.321964

Un algoritmo distribuido para la misma configuración se debe a Turau y Köhler:

Volker Turau y Sven Köhler. Algoritmo distribuido para la distancia mínima-k Dominación en los árboles. Journal of Graph Algorithms and Applications, 19 (1): 223–242,5 (ver http://jgaa.info/getPaper?id=354 )