Pytania otagowane jako fixed-parameter-tractable

algorytmy dla sparametryzowanych problemów, w których czas wykonywania jest wielomianowy w rozmiarze wejściowym, ale zależy arbitralnie od parametru

4
Otwarte problemy związane z izomorfizmem grafowym
Obecnie prowadzę przegląd literatury dotyczący problemu izomorfizmu grafowego (GI). Chciałbym poznać kilka otwartych pytań związanych z następującymi zagadnieniami Jakie są parametry wykresu, dla których ustalona zdolność pomiarowa GI jest otwartym problemem. Jakie są parametry wykresu, przez ustalenie ich wielomianowej zdolności do rozwiązywania GI nie jest znana. Złożoność GI, gdy jest …
2
Biorąc pod uwagę 4-cyklowy wykres , czy możemy ustalić, czy ma on 3-cykl w czasie kwadratowym?
Problem z rowem jest następujący:kkk Instancja: Niekierowany wykres z wierzchołkami i do n \ wybierz 2 krawędzie.nsolsolGnnn( n2))(n2))n \choose 2 Pytanie: Czy w G istnieje (właściwy) cykl K ?kkksolsolG Tło: Dla każdego ustalonego kkk możemy rozwiązać cykl 2 tys2)k2k w czasie O ( n2))O(n2))O(n^2) . Raphael Yuster, Uri Zwick: Znalezienie …
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, …
1
Elementarne granice parametru w ciągliwości parametrów stałych?
W definicji (silnej) ciągliwości parametrów stałych ustalony czas jest wyrażeniem postaci gdzie instancja wejściowa to ( x , k ) z parametrem k , p jest wielomianem, a f jest funkcją obliczalną .f(k).p(|x|),f(k).p(|x|),f(k).p(|x|),(x,k)(x,k)(x,k)kkkpppfff Możliwe jest zastąpienie wymogu obliczeniowego dla innymi klasami funkcji, o ile pojęcie redukcji jest podobnie ograniczone. (Na …
2
Zależność między stałym parametrem a algorytmem aproksymacyjnym
Stały parametr i przybliżenie to zupełnie inne podejścia do rozwiązywania trudnych problemów. Mają inną motywację. Przybliżenie szuka szybszego wyniku dzięki przybliżonemu rozwiązaniu. Naprawiono parametr szuka dokładnego rozwiązania ze złożonością czasową pod względem wykładniczej lub jakiejś funkcji k i funkcji wielomianowej n, gdzie n jest wielkością wejściową, a k jest parametrem. …
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?
1
Jakieś wyniki na binarnym CSP typu boolean wykraczają poza ustalalność parametrów prawie problemu 2SAT?
Niech będzie formułą 2CNF, a k nieujemną liczbą całkowitą. Jest udowodnione w tym artykule , że problem z podjęciem decyzji, czy można usunąć co najwyżej k klauzul aby φ satisfable określony jest parametr tractable, gdzie k jest parametrem. Moje pytanie brzmi: czy są jakieś prace, które uogólniają ten wynik na …
1
Domysł: Wszystkie języki FPT NP-complete mają stały parametr izomorficzny
Hipoteza Bermana – Hartmanisa: wszystkie języki NP-zupełne wyglądają podobnie, w tym sensie, że mogą być ze sobą powiązane przez wielomianowe izomorfizmy czasowe [1]. Interesuje mnie bardziej szczegółowa wersja „czasu wielomianowego”, to znaczy, jeśli zastosujemy sparametryzowane redukcje. Problem sparametryzowany to podzbiór , gdzie jest skończonym alfabetem, a to zbiór liczb nieujemnych. …
2
Które problemy z grafem są trudne dla na wykresach skierowanych (/ ważonych), ale FPT na wykresach niekierowanych (/ nieważonych)?
Po równoważnych pytaniach dotyczących kompletności NP (patrz pytanie wagi i pytanie kierowane ) zastanawiałem się, w jaki sposób atrybuty te wpływają na sparametryzowane problemy. Które problemy z twardym grafem są trudne dla na grafach ukierunkowanych, ale stały parametr można traktować na grafach bezkierunkowych?NPNPNPW[1]W[1]W[1] Które problemy z twardym grafem są trudne …
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.