Точные алгоритмы для r-доминирующего множества на графах ограниченной ширины

Учитывая график, , я хочу , чтобы найти оптимальный г -domination для G . То есть, я хочу подмножество S из V таким образом, что все вершины в G находятся на расстоянии не более чем г от некоторой вершины в S , при сведении к минимуму размера S .$G = (V, E)$$r$$G$$S$$V$$G$$r$$S$$S$

Из того, что я проверил до сих пор, я получил следующее: Существует связанная с этим проблема нахождения -центра в графе, который является подмножеством размера S не более k таким, что все вершины графа на расстоянии не более r от некоторой вершины в S (здесь оба | S | ≤ k и r являются частями входных данных), для которых Demaine et al . иметь алгоритм FPT для плоских графов. В противном случае задача будет W [ 2 ] -твердой для четного r = 1 .$(k,r)$$S$$k$$r$$S$$|S| \leq k$$r$$W[2]$$r = 1$

Известно ли что-нибудь о точной сложности задачи доминирования для графов с ограниченной шириной дерева или даже только для деревьев? (Является ли r- доминирование MSO определимым? Обычная задача о k- доминирующем множестве определяется MSO - что позволило бы использовать теорему Курселя, чтобы сделать вывод, что для задачи существует линейный алгоритм времени). Известны ли какие-либо условные результаты по этой проблеме?$r$$r$$k$

(Оптимальное) доминирование для G - это (оптимальное) доминирование для r- й степени G r и наоборот ( G r получается из $r$$G$$r$$G^r$$G^r$$G$ путем добавления новых ребер между различными вершинами расстояния не более ).$r$

Следующие факты хорошо известны: (1) Все степени сильно хордового графа являются сильно хордовыми (А. Любив, магистерская работа; см. Также Dahlhaus & Duchet, О сильно хордовых графах, Ars Combin. 24 B (1987) 23-30 ) и (2) Доминирование разрешимо в линейном времени для сильно хордовых графов (М. Фарбер. Доминирование, независимое доминирование и двойственность в сильно хордовых графах, Discrete Appl. Math., 7 (1984) 115–130). Следовательно, доминирование разрешимо за полиномиальное время для сильно хордовых графов, в частности, для деревьев ( r фиксировано или нет).$r$$r$

Гурский & Ванка доказана в данной работе , что Клика-ширина составляет не более 2 ⋅ ( г + 1 ) ТВта ( G ) + 1 - 2 , где TW ( G ) является дерево-шириной G . Таким образом, при фиксированном г , то г - й степеней ограниченных деревьев ширины графов имеют ограниченную ширину клике. Следовательно, при фиксированном г , г -domination разрешима в полиномиальное время для ограниченных дерева ширины графов (по теореме Courcelle в). $G^r$$2\cdot (r+1)^{\text{tw}(G)+1}−2$$\text{tw}(G)$$G$$r$$r$$r$$r$

Для этой задачи довольно просто выполнить динамическое программирование на графиках ширины дерева . Можно сохранить для каждой вершины в сумке кратчайшее расстояние до некоторой вершины в частичном решении и расстояние до будущего решения, необходимое для доминирования над недоминированными вершинами.$k$

В сумме это дает размер таблицы поэтому для фиксированного r эта проблема FPT параметризуется по ширине дерева, однако, если r не зафиксировано, это становится алгоритмом XP. Насколько мне известно, вопрос о том, является ли эта проблема FPT для всех значений r, является открытым.$O(r^k)$$r$$r$$r$

Давар и Кройцер показали, что задача задается с фиксированным параметром на нигде не плотных классах графов, включая плоские графы, графы ограниченной (локальной) ширины дерева и все классы с (локально) исключенными минорами.

Dvorak has shown that there is a polynomial time constant factor approximation for classes of bounded expansion, which includes the planar graphs, graphs of bounded tree-width and all classes with excluded minors.

Есть недавняя статья Гленкора Боррадайл, Хунг Ле: Optimal Dynamic Program for r-Domination Problems over Tree Decompositions (IPEC 2016). Here they show that there is an algorithm that given as input a graph $G$целое число $r$, and a tree-decomposition of $G$ of width $w$, computes an optimal $r$-dominating set of $G$ in time $O((2r+1)^wn)$. Furthermore, they show that this is the best one can do, in the following sense: an algorithm with running time $O((2r+1-\epsilon)^wn^{O(1)})$ for $\epsilon > 0$ would contradict the Strong Exponential Time Hypothesis.

A linear sequential algorithm to compute a optimal r-domination for a tree is due to Slater:

P. Slater. R-domination in graphs. J. ACM, 23(3):446–450, July 1976. doi:10.1145/321958.321964

A distributed algorithm for the same setting is due to Turau and Köhler:

Volker Turau and Sven Köhler. A Distributed Algorithm for Minimum Distance-k Domination in Trees. Journal of Graph Algorithms and Applications, 19(1):223–242,5 (see http://jgaa.info/getPaper?id=354)