Twardość sparametryzowanego CLIQUE?

17

Niech 0p1 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?p
sGtGsp(t2)
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 spppp01pp1/2p T(t,s1)

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 ppppp

To pytanie powstało z pokrewnego pytania dotyczącego hipergraphów, ale samo w sobie wydaje się interesujące.

András Salamon
źródło
1
interesujące pytanie !
Suresh Venkat
Czy pa jest liczbą rzeczywistą między 0 a 1, czy może p może być funkcją t?
Robin Kothari,
@Robin: Nie określiłem, oba byłyby interesujące.
András Salamon,
3
Jeśli proporcja krawędzi jest górną granicą (a nie dokładnym wymogiem zliczania lub dolną granicą), to dla dowolnej stałej problem ten jest trudny do NP przez redukcję z CLIQUE: Dodaj wystarczająco duży zestaw izolowanych wierzchołków . Czy wymóg, aby krawędzie liczb były równe podanemu wyrażeniu? Lub jakiej rażąco oczywistej rzeczy brakuje mi? :-)0<p<1
gphilip
1
@ gphilip: Jak zauważyłeś, zmniejszenie jest natychmiastowe, jeśli proporcja jest tylko górną granicą; dlatego pytanie jest sformułowane dokładną proporcją.
András Salamon,

Odpowiedzi:

14

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.

  1. Jeśli s < k , rozwiązujemy problem CLIQUE w czasie O ( n s ). Jeśli istnieje klika wielkości co najmniej s , tworzymy stałą instancję typu tak. W przeciwnym razie produkujemy stały brak wystąpienia.
  2. Jeśli n < s , tworzymy stały brak wystąpienia.
  3. Jeśli nsk , dodajemy do G a ( k -1) wykres partycypacyjny, gdzie każdy zestaw składa się z n wierzchołków, które mają dokładnie krawędzi i wygeneruj ten wykres.p(nk2)m

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 nsk , 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)m0

m(n2)p(nk2)(n2)

p(nk2)m<n2(k12). (Note that the right-hand side is the number of edges in the complete (k−1)-partite graph Kn,…,n.)

Proof. Since x<x+1 and m ≥ 0, it suffices if we prove p(nk2)+1n2(k12), or equivalently n2(k−1)(k−2) − pnk(nk−1) − 2 ≥ 0. Since p < (1−1/k)(1−2/k), we have

n2(k1)(k2)pnk(nk1)2
n2(k1)(k2)n(n1k)(k1)(k2)2
=nk(k1)(k2)2(k1)(k2)20.
QED.

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.

Tsuyoshi Ito
źródło
this is closest to the specific phrasing, so thanks for tackling it. Case 3 is closest to what I had in mind. However, I don't follow the calculation -- could you expand a little?
András Salamon
@András Salamon: Done.
Tsuyoshi Ito
15

If p 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 on log2t 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.

If p is a constant then it's always NP hard as gphilip said.

Boaz Barak
źródło