Niech 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?
Gs
Instancja CLIQUE zawiera proporcję spośród wszystkich możliwych krawędzi. Wyraźnie CLIQUE jest łatwy dla niektórych wartości . CLIQUE zawiera tylko całkowicie odłączone wykresy, a CLIQUE zawiera pełne wykresy. W obu przypadkach CLIQUE można ustalić w czasie liniowym. Z drugiej strony, dla wartości zbliżonych do , CLIQUE jest NP-twardy przez redukcję z samego CLIQUE: zasadniczo wystarczy przyjąć rozłączny związek z wykresem Turána . P P P 0 1 P P 1 / 2 s
Moje pytanie:
Czy CLIQUE ma wartość PTIME lub NP-complete dla każdej wartości ? Czy są wartości dla których CLIQUE ma pośrednią złożoność (jeśli P ≠ NP)? p p p
To pytanie powstało z pokrewnego pytania dotyczącego hipergraphów, ale samo w sobie wydaje się interesujące.
źródło
Odpowiedzi:
Zakładam, że liczba w definicji problemu CLIQUEpjest dokładnie równa liczbie krawędzi na wykresie, w przeciwieństwie do komentarza gphilipa do pytania.⌈p(t2)⌉
Problem CLIQUE p jest NP-zupełny dla dowolnej racjonalnej stałej 0 < p <1 poprzez zmniejszenie od zwykłego problemu CLIQUE. (Założenie, że p jest racjonalne, jest wymagane tylko po to, aby można było obliczyć z N w funkcji wielomianu czasowego w N ).⌈pN⌉
Niech k ≥3 będzie liczbą całkowitą spełniającą zarówno k 2 ≥1 / p, jak i (1−1 / k ) (1−2 / k )> p . Biorąc pod uwagę wykres G z n wierzchołkami i krawędziami m wraz z wartością progową s , redukcja działa w następujący sposób.
Należy zauważyć, że w przypadku 1 odbywa O ( N K -1 ) czas, który jest wielomian n dla każdego p . Przypadek 3 jest możliwy, ponieważ jeśli n ≥ s ≥ k , to jest nieujemne i co najwyżej liczba krawędzi na pełnym (k-1) wykresie stronniczym Kn,…,n,jak pokazano w dwóch poniższych zastrzeżeniach.⌈p(nk2)⌉−m
Roszczenie 1 . .⌈p(nk2)⌉−m≥0
Proof. Since⌈x⌉<x+1 and m ≥ 0, it suffices if we prove p(nk2)+1≤n2(k−12) , or equivalently n2(k−1)(k−2) − pnk(nk−1) − 2 ≥ 0. Since p < (1−1/k)(1−2/k), we have
Edit: The reduction in Revision 1 had an error; it sometimes required a graph with negative number of edges (when p was small). This error is fixed now.
źródło
Ifp can be a function of t , then the problem can be intermediate. Set up p so that the number of edges will be say log4t . Then obviously s can be at most log2t and hence there is a tlog2t algorithm for this problem, meaning that the problem (under standard assumptions, say SAT doesn't have subexponential algorithms) cannot be NP hard.
On the other hand, this problem is harder than the standard clique problem onlog2t vertices (you can always place all the edges on those vertices and ignore the rest). And so again, under the same assumption the problem doesn't have a polynomial time algorithm.
Ifp is a constant then it's always NP hard as gphilip said.
źródło