Pytania otagowane jako parameterized-complexity

Badanie złożoności obliczeniowej problemów w odniesieniu do więcej niż jednego parametru.

3
Czy istnieje rozsądne pojęcie algorytmu aproksymacyjnego dla nierozwiązywalnego problemu?
Niektóre problemy są nierozstrzygalne, ale mimo to można poczynić pewne postępy w ich rozwiązywaniu. Na przykład problem zatrzymania jest nierozstrzygalny, ale można poczynić praktyczne postępy w tworzeniu narzędzi do wykrywania potencjalnych nieskończonych pętli w kodzie. Problemy z układaniem płytek są często nierozstrzygalne (np. Czy ta płytka poliomino ma jakiś prostokąt?), …
3
Sparametryzowana złożoność zestawu uderzeń w skończonym wymiarze VC
Interesuje mnie sparametryzowana złożoność problemu, który nazywam d-Dimensional Hitting Set: biorąc pod uwagę przestrzeń zakresu (tj. Układ zestawu / hipergraph) S = (X, R) mający wymiar VC co najwyżej d dodatnia liczba całkowita k, czy X zawiera podzbiór wielkości k, który uderza w każdy zakres w R? Sparametryzowana wersja problemu …
3
Wykorzystanie złożoności Kołmogorowa jako wejściowego „rozmiaru”
SSSI(n)={w∈S:|w|=n}I(n)={w∈S:|w|=n}I(n) = \{w \in S : |w| = n\}nnnT(w)T(w)T(w)AAAwwwAAAfn=maxw∈I(n)T(w).fn=maxw∈I(n)T(w). f_n = \max_{w \in I(n)} T(w). Zdefiniujmy teraz zbiory wszystkich danych wejściowych o złożoności Kołmogorowa , i zdefiniujmy sekwencję Tutaj jest średnią sekwencją czasu pracy dla , z wyjątkiem przypadków, gdy „rozmiar” danych wejściowych jest złożonością Kołmogorowa, a nie ich długością.n …
1
Algorytmiczne zalety szerokości ścieżki w porównaniu do szerokości
Treewidth odgrywa ważną rolę w algorytmach FPT, częściowo dlatego, że wiele problemów jest FPT parametryzowanych przez treewidth. Powiązanym, bardziej ograniczonym pojęciem jest szerokość ścieżki. Jeśli wykres ma szerokość ścieżki , ma również szerokość co najwyżej , podczas gdy w kierunku przeciwnym, szerokość oznacza tylko szerokość ścieżki co najwyżej a to …
2
Sparametryzowana złożoność numeru przecięcia wykresu
Co jeśli wiadomo o sparametryzowanej złożoności obliczania numeru przecięcia wykresu (najmniejszej liczby klików potrzebnych do pokrycia wszystkich jego krawędzi)? Od dawna wiadomo, że jest NP-kompletny, i oczywiście FPT, ponieważ ma jądro: jeśli możesz pokryć wykres klikami, to istnieje co najwyżej różnych zamkniętych sąsiedztw wierzchołków (dwa wierzchołki mają te same sąsiedztwa …
2
Twardość sparametryzowanego CLIQUE?
Niech 0≤p≤10≤p≤10\le p\le 1 i rozważmy problem decyzyjny Klika P Wejście: całkowita s , wykres G z T wierzchołki krawędzie Pytanie: sposób zawierać klika na co najmniej wierzchołki?pp_p sssGGGtttGs⌈p(t2)⌉⌈p(t2)⌉\lceil p\binom{t}{2} \rceil GGGsss Instancja CLIQUE zawiera proporcję spośród wszystkich możliwych krawędzi. Wyraźnie CLIQUE jest łatwy dla niektórych wartości . CLIQUE zawiera …
4
Sparametryzowany algorytm znajdowania biklików
Biorąc pod uwagę nieukierowany wykres nnn wierzchołka, jaki jest najbardziej znany środowisko uruchomieniowe dla znalezienia podrozdziału, który jest dwukolorową k × kk×kk\times k ? Czy istnieją szybsze algorytmy parametryzowane niż algorytm polegający na „zgadywaniu” jednej strony biclique i sprawdzanie, czy występuje co najmniej k innych wierzchołków przypadających na wszystkie z …
1
Wyrażenia o szerokości kliki z głębokością logarytmiczną
Kiedy otrzymujemy rozkład drzewa wykresu o szerokości , istnieje kilka sposobów, dzięki którym możemy go uczynić „ładnym”. W szczególności wiadomo, że można go przekształcić w rozkład drzewa, w którym drzewo jest binarne, a jego wysokość wynosi . Można to osiągnąć przy zachowaniu szerokości rozkładu co najwyżej . (Patrz np. „Algorytmy …
5
Dokładne algorytmy dla zestawu R-Dominującego na wykresach ograniczonej Treewidth
Biorąc pod uwagę wykres, G=(V,E)G=(V,E)G = (V, E) , to znaleźć optymalną rrr -domination dla GGG . Oznacza to, że chce podzbiór SSS o VVV tak, że wszystkie wierzchołki GGG znajdują się w odległości co najwyżej rrr z pewnym wierzchołka w SSS , przy jednoczesnym zminimalizowaniu rozmiaru .SSS Z tego, …
2
Naturalne kompletne problemy na wyższych poziomach hierarchii
-hierarchy hierarchia klas złożoność w sparametryzowanej złożoności patrz Zoo złożoność definicje. Alternatywna definicja definiuje przy użyciu ważonej definiowalności Fagina dla logiki pierwszego rzędu, patrz podręcznik Fluma i Grohe .W [ t ] W [ t ] Π tWW\mathsf{W}W[t]W[t]\mathsf{W}[t]W[t]W[t]\mathsf{W}[t]ΠtΠt\Pi_t Dla najniższych klas i , znanych jest wiele naturalnych kompletnych problemów, np. …
2
Edytuj odległość za pomocą operacji przesuwania
Motywacja: Współautor redaguje manuskrypt i chciałbym zobaczyć jasne podsumowanie edycji. Wszystkie narzędzia podobne do „diff” są zwykle bezużyteczne, jeśli zarówno przenosisz tekst (np. Reorganizując strukturę), jak i edytujesz lokalnie. Czy to naprawdę takie trudne? Definicje: Chciałbym znaleźć minimalną odległość edycji, gdzie dozwolone operacje to: „tanie” operacje: dodaj / zmień / …
5
Twardość problemów FPT
Osłonę wierzchołka można łatwo zredukować do zestawu niezależnego i odwrotnie. Jednak w kontekście sparametryzowanej złożoności zestaw niezależny jest trudniejszy niż osłona wierzchołka. Jądro z wierzchołków istnieje problem pokrycia wierzchołkowego, ale niezależnego zestawu jest biała 1 dysku.2k2k2k Jak zmienia się natura Independent Set w kontekście FPT i dlaczego?
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.