Dokładne algorytmy dla zestawu R-Dominującego na wykresach ograniczonej Treewidth

Biorąc pod uwagę wykres, $G = (V, E)$ , to znaleźć optymalną $r$ -domination dla $G$ . Oznacza to, że chce podzbiór $S$ o $V$ tak, że wszystkie wierzchołki $G$ znajdują się w odległości co najwyżej $r$ z pewnym wierzchołka w $S$ , przy jednoczesnym zminimalizowaniu rozmiaru .$S$

Z tego, co sprawdziłem do tej pory, otrzymałem następujące: Istnieje związany z tym problem znalezienia centrum na wykresie, który jest podzbiorem o wielkości co najwyżej$(k,r)$$S$$k$ taki, że wszystkie wierzchołki na wykresie są w odległości atmost $r$ od pewnego wierzchołka w $S$ (tutaj oba $|S| \leq k$ i $r$ są częściami danych wejściowych), dla których Demaine i in . mieć algorytm FPT dla grafów płaskich. W przeciwnym razie problemem jest $W[2]$ twardy dla parzystego $r = 1$ .

Czy wiadomo coś o dokładnej złożoności problemu -dominacji dla ograniczonych wykresów szerokości drzewa, a nawet tylko drzew? (Czy można zdefiniować MS- r -dominacja r ? Zwykły problem z zestawem -dominacji k jest definiowalny przez MSO - co pozwoliłoby następnie użyć twierdzenia Courcelle'a do stwierdzenia, że ​​istnieje liniowy algorytm czasu dla problemu). Czy znane są wyniki twardości warunkowej dotyczące tego problemu?$r$$r$$k$

An (optymalna) -domination dla G JEST (optymalna) dominacja dla R do potęgi G R i odwrotnie ( G r uzyskuje się z G poprzez dodanie nowych krawędzi pomiędzy wierzchołkami różnych odległości co najwyżej R ).$r$$G$$r$$G^r$$G^r$$G$$r$

Dobrze znane są następujące fakty: (1) Wszystkie moce wykresu silnie akordowego są silnie akordowe (A. Lubiw, praca magisterska; patrz także Dahlhaus i Duchet, Na wykresach silnie akordowych, Ars Combin. 24 B (1987) 23-30 ) oraz (2) Dominacja jest rozwiązywalna w czasie liniowym dla wykresów silnie akordowych (M. Farber. Dominacja, niezależna dominacja i dualność na wykresach silnie akordowych, Discrete Appl. Math., 7 (1984) 115–130). Stąd -dominacja może być rozwiązana w czasie wielomianowym dla wykresów silnie akordowych, w szczególności dla drzew ( r ustalonych lub nie).$r$$r$

Gurski i Wanke udowodnione w niniejszym dokumencie , że klika-szerokości wynosi co najwyżej 2 ⋅ ( r + 1 ) tw ( G ) + 1 - 2 , w którym tw ( G ) jest drzewa szerokość G . Tak więc, dla ustalonego r The R th uprawnień ograniczonych drzew szerokości wykresach zostały ograniczone kliki szerokości. Stąd, dla stałej r , r -dominacja jest rozwiązywalna w czasie wielomianowym dla ograniczonych grafów szerokości drzewa (według twierdzenia Courcelle'a). $G^r$$2\cdot (r+1)^{\text{tw}(G)+1}−2$$\text{tw}(G)$$G$$r$$r$$r$$r$

W przypadku tego problemu programowanie dynamiczne na wykresach szerokości jest dość łatwe . Dla każdego wierzchołka w torbie można zachować jak najkrótszą odległość do niektórych wierzchołków w rozwiązaniu częściowym oraz odległość do przyszłego rozwiązania potrzebną do zdominowania niezdominowanych wierzchołków.$k$

To w sumie daje wielkość stołu z tak dla ustalonego r Problem ten jest parametryzowane przez FPT treewidth, jednak jeśli R nie jest stała staje algorytm XP. O ile wiem, pytanie, czy ten problem dotyczy FPT dla wszystkich wartości r, jest otwarte.$O(r^k)$$r$$r$$r$

Dawar i Kreutzer wykazali, że problem można rozwiązać przy pomocy stałych parametrów nigdzie gęstych klas grafów, w tym grafów płaskich, grafów ograniczonej (lokalnej) szerokości drzewa i wszystkich klas z (lokalnie) wykluczonymi nieletnimi.

Dvorak wykazał, że istnieje wielomianowe przybliżenie współczynnika stałej czasowej dla klas ograniczonej ekspansji, która obejmuje wykresy płaskie, wykresy ograniczonej szerokości drzewa i wszystkie klasy z wykluczonymi nieletnimi.

Istnieje niedawny artykuł Glencory Borradaile, Hung Le: Optymalny program dynamiczny dla problemów z dominacją r nad rozkładami drzew (IPEC 2016). Tutaj pokazują, że nie jest algorytmem, który podano jako wejście wykres , oznacza liczbę całkowitą R i drzewa rozkładu G szerokości wagowo , oblicza się optymalną R -dominating zestaw G w czasie O ( ( 2 r + 1 ) w n ) . Ponadto pokazują, że jest to najlepsze, co można zrobić, w następującym znaczeniu: algorytm z czasem działania O ( ( $G$$r$$G$$w$$r$$G$$O((2r+1)^wn)$ dla ϵ > 0 byłoby sprzeczne z hipotezą silnego czasu wykładniczego.$O((2r+1-\epsilon)^wn^{O(1)})$$\epsilon > 0$

Liniowy algorytm sekwencyjny do obliczania optymalnej dominacji r dla drzewa wynika ze Slatera:

P. Slater. Dominacja R na wykresach. J. ACM, 23 (3): 446–450, lipiec 1976 r. Doi: 10.1145 / 321958.321964

Algorytm rozproszony dla tego samego ustawienia wynika z Turau i Köhler:

Volker Turau i Sven Köhler. Algorytm rozproszony dla minimalnej odległości-k Dominacja w drzewach. Journal of Graph Algorytmy and Applications, 19 (1): 223–242,5 (patrz http://jgaa.info/getPaper?id=354 )