Genaue Algorithmen für die r-dominierende Menge in Bounded Treewidth-Diagrammen

Mit einem Graphen möchte ich eine optimale r- Dominanz für G finden . Das heißt, ich möchte eine Teilmenge S von V, so dass alle Scheitelpunkte in G höchstens r von einem Scheitelpunkt in $G = (V, E)$$r$$G$$S$$V$$G$$r$$S$ , während die Größe von minimiert wird .$S$

Nach dem, was ich bisher überprüft habe, habe ich Folgendes festgestellt: Es besteht das damit verbundene Problem, ein -Zentrum in einem Graphen zu finden, das eine Teilmenge S mit einer Größe von höchstens k ist , sodass alle Scheitelpunkte im Graphen gleich sind in einem Abstand von höchstens r von einem Scheitelpunkt in S (hier sind sowohl | S | ≤ k als auch r Teile der Eingabe), für die Demaine et al . haben einen FPT-Algorithmus für planare Graphen. Ansonsten ist das Problem W [ 2 ] -hart für gerade r = 1 .$(k,r)$$S$$k$$r$$S$$|S| \leq k$$r$$W[2]$$r = 1$

Ist irgendetwas über die genaue Komplexität des Dominanz-Problems für Diagramme mit begrenzter Baumbreite oder nur für Bäume bekannt? (Ist r- Dominanz-MSO definierbar? Das übliche k- Dominanz-Mengenproblem ist MSO-definierbar. Dies würde es dann ermöglichen, Courcelles Theorem zu verwenden, um zu folgern, dass es einen linearen Zeitalgorithmus für das Problem gibt.) Gibt es bedingte Härteergebnisse für dieses Problem?$r$$r$$k$

Eine (optimale) Dominanz für G ist eine (optimale) Dominanz für die r- te Potenz G r und umgekehrt ( G r wird aus G erhalten, indem neue Kanten zwischen bestimmten Entfernungspunkten höchstens r hinzugefügt werden$r$$G$$r$$G^r$$G^r$$G$$r$ ).

Die folgenden Tatsachen sind allgemein bekannt: (1) Alle Potenzen eines stark akkordischen Graphen sind stark akkordisch (A. Lubiw, Masterarbeit; siehe auch Dahlhaus & Duchet, Über stark akkordische Graphen, Ars Combin. 24 B (1987) 23-30 ) und (2) Domination ist in linearer Zeit für stark akkordische Graphen lösbar (M. Farber. Domination, unabhängige Dominanz und Dualität in stark akkordischen Graphen, Discrete Appl. Math., 7 (1984) 115–130). Daher ist die Dominanz für stark akkordische Graphen, insbesondere für Bäume ( r fest oder nicht fest) , in Polynomzeit lösbar .$r$$r$

Gurski & Wanke haben in dieser Arbeit bewiesen , dass die Clique-Breite von höchstens 2 ⋅ ( r + 1 ) tw ( G ) + 1 - 2 beträgt , wobei tw ( G ) die Baumbreite von G ist . Für ein festes r haben die r- ten Potenzen von Diagrammen mit begrenzter Baumbreite die Cliquenbreite begrenzt. Für ein festes r ist die r -Dominierung in der Polynomzeit für Graphen mit begrenzter Baumbreite lösbar (gemäß Courcelle-Theorem). $G^r$$2\cdot (r+1)^{\text{tw}(G)+1}−2$$\text{tw}(G)$$G$$r$$r$$r$$r$

Für dieses Problem ist es recht einfach, dynamische Programmierung in Graphen der Baumbreite durchzuführen . Man kann für jeden Scheitelpunkt in einem Beutel die kürzeste Entfernung zu einem Scheitelpunkt in der Teillösung und die Entfernung zu einer zukünftigen Lösung, die benötigt wird, um die undominierten Scheitelpunkte zu dominieren, aufbewahren.$k$

Dies ergibt insgesamt eine Tabellengröße von so dass dieses Problem für festes r durch die Baumbreite FPT-parametrisiert wird. Wenn jedoch r nicht fest ist, wird dies zu einem XP-Algorithmus. Soweit ich weiß, ist die Frage offen, ob es sich bei diesem Problem um eine FPT für alle Werte von r handelt.$O(r^k)$$r$$r$$r$

Dawar und Kreutzer haben gezeigt, dass das Problem auf nirgendwo dichten Klassen von Graphen, die die planaren Graphen, die Graphen mit begrenzter (lokaler) Baumbreite und alle Klassen mit (lokal ausgeschlossenen) Minderjährigen umfassen, über feste Parameter verfolgbar ist.

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.

There is a recent paper by Glencora Borradaile, Hung Le: 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$, an integer $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)