Gepflanzte Clique in G (n, p), variierend p

9

In dem Problem der gepflanzten Cliquen muss man eine Clique wiederherstellen, die in einem Erdos-Renyi-Zufallsgraphen gepflanzt ist . Dies wurde hauptsächlich für . In diesem Fall ist bekannt, dass es polynomial lösbar ist, wenn und für hart vermutet wird .kG(n,p)p=12k>nk<n

Meine Frage ist: Was ist über andere Werte von bekannt / geglaubt ? Insbesondere wenn eine Konstante in ? Gibt es Hinweise darauf, dass es für jeden solchen Wert von ein für das das Problem rechenintensiv ist?pp[0,1]]k = n αpk=nα

Referenzen wären besonders hilfreich, da es mir nicht gelungen ist, Literatur zu finden, die das Problem für andere Werte als .p=12

srd
quelle
Ja, es ist schwierig für einige Parameter, die auf dem NP-Phänomen des vollständigen Übergangspunkts basieren, das für SAT genauer untersucht wurde, aber auch für das Cliquenproblem gilt und dort einige / weniger untersucht wurde. Dies hängt eng mit der Suche nach Untergrenzen für monotone Schaltkreise für das Cliquenproblem und die Slice-Funktionen zusammen. Es gibt ein paar verwandte Fragen auf der Website, können sie ausgraben. Das kürzlich erschienene Papier von Rossman über die Clique-Funktionshärte ist relevant. etc ... könnte später zur Antwort kommen, je nachdem, ob andere auftauchen ...
vzn
Diese Q / A- Härte der parametrisierten Clique tcs.se sollte Ihre Frage direkt beantworten. Antwort in Theoretical Computer Science Chat für weitere Diskussion
vzn
1
Vielen Dank. Ich habe mich jedoch hauptsächlich mit der gepflanzten Version befasst und nicht mit der Worst-Case-Version (die, wie Sie sagen, NP-Konstante für konstantes p ist).
srd
ok, es scheint, dass "gepflanzte Clique" im Allgemeinen auf G (n, ½) beschränkt ist, wie Sie in diesem kürzlich erschienenen Artikel Statistical Algorithms and a Lower Bound for Detection Planted Clique von Feldman et al betrachte p ≠ ½. Das Gesamtproblem scheint "nahe" daran zu liegen, Cliquen von einiger Größe in einem G (n, p) -Diagramm für einige Auswahlmöglichkeiten von Parametern zu finden (letzteres wird anscheinend viel genauer untersucht als im verknüpften tcs.se pg), aber ich habe das nicht gesehen Verbindung an anderer Stelle aufgezeigt oder ausgearbeitet / detailliert.
vzn

Antworten:

9

Wenn konstant ist, ist die Größe der maximalen Clique im -Modell fast überall ein konstantes Vielfaches von , wobei die Konstante proportional zu . (Siehe Bollobás, S.283 und Korollar 11.2.) Das Ändern von sollte daher die Härte des Pflanzens einer Clique mit Eckpunkten nicht beeinflussen, solange die Clique zu klein ist, als dass ein vorhandener algorithmischer Ansatz funktionieren könnte. Ich erwarte daher, dass sich bei konstanter die Härte von Planted Clique genauso verhält wie im Fall , obwohl es möglich ist, dass sich der Fall von sehr nahe bei 0 oder 1 anders verhält.G ( n , p ) log n log ( 1 / p ) p ω ( log n ) p 1 / 2 p = 1 / 2 ppG(n,p)LognLog(1/.p)pω(Logn)p1/.2p=1/.2p

Insbesondere gilt für der gleiche Schwellenwert von für für die Größe der gepflanzten Clique, oberhalb dessen das Problem zur Polynomzeit wird. Der Wert von hier (und kein anderer Wert), da die Lovász-Theta-Funktion von fast sicher zwischen und durch ein Ergebnis von Juhász. Der Algorithmus von Feige und Krauthgamer verwendet die Lovász-Theta-Funktion, um eine größte Clique zu finden und zu zertifizieren. Daher stützt er sich auf diese Schwellengröße für die gepflanzte Clique.Ω ( n α ) , α = 1 / 2 α 1 / 2 G ( n , p ) 0,5 p1/.2Ω(nα)α=1/.2α1/.2G(n,p)0,5(1- -p)/.pn2(1- -p)/.pn

Natürlich kann es einen anderen Algorithmus geben, der die Lovász-Theta-Funktion nicht verwendet, und der für Werte von weit von eine gepflanzte Clique mit beispielsweise Eckpunkten finden kann. Soweit ich das beurteilen kann, ist dies noch offen.p1/.2n1/.3

Feige und Krauthgamer diskutieren auch, wenn nicht konstant ist, sondern von abhängt und entweder nahe bei 0 oder nahe bei 1 liegt. In diesen Fällen gibt es andere Ansätze, um gepflanzte Cliquen zu finden, und die Schwellengröße ist unterschiedlich.pn

  • Béla Bollobás, Random Graphs (2. Auflage), Cambridge University Press, 2001.
  • Ferenc Juhász, Das asymptotische Verhalten der Lovász' Funktion für Zufallsgraphenϑ , Combinatorica 2 (2) 153–155, 1982. doi: 10.1007 / BF02579314
  • Uriel Feige und Robert Krauthgamer, Finden und Zertifizieren einer großen versteckten Clique in einem halbzufälligen Graphen , Random Structures & Algorithms 16 (2) 195–208, 2000. doi: 10.1002 / (SICI) 1098-2418 (200003) 16: 2 <195 :: AID-RSA5> 3.0.CO; 2-A
András Salamon
quelle
Vielen Dank. Dies scheint den Stand der Technik zusammenzufassen und zu bestätigen, dass nichts zu Bestimmtes bekannt ist. Der beste Beweis dafür, dass sich das Problem ähnlich verhält, scheint der Wert der Lovasz-Theta-Funktion zu sein, wie Sie hervorheben.
srd
1

gepflanzte Clique für ist ein Sonderfall dieses Problems und neuer Ergebnisse (untere Schranken), wie auf Seite 2 usw. angegeben, und enthält verwandte Verweise. (2015)p12

Wir zeigen, dass unter der Annahme der (deterministischen) Exponentialzeithypothese die Unterscheidung zwischen einem Graphen mit einer induzierten Clique und einem Graphen, in dem alle k- Subgraphen eine Dichte von höchstens 1 - ε haben , n ˜ Ω ( log n ) Zeit erfordert .kk1εnΩ~(logn)

vzn
quelle
0

Hier ist eine neue Arbeit, die einen Algorithmus für beliebige p ≠ ½ enthält, der auf einem SVD-Algorithmus basiert. Siehe S.4 für die Analyse der versteckten (gepflanzten) Clique.

EIN EINFACHER SVD-ALGORITHMUS ZUM FINDEN VERSTECKTER TEILE Van Vu

Abstrakt. Das Finden einer versteckten Partition in einer zufälligen Umgebung ist ein allgemeines und wichtiges Problem, das als Teilprobleme viele berühmte Fragen enthält, wie das Finden einer versteckten Clique, das Finden einer versteckten Färbung, das Finden einer versteckten Bipartition usw. In diesem Artikel stellen wir eine einfache SVD bereit Algorithmus für diesen Zweck, Beantwortung einer Frage von McSherry. Dieser Algorithmus ist sehr einfach zu implementieren und funktioniert für spärliche Graphen mit optimaler Dichte.

vzn
quelle
2
p=1/.2ppΩ(n)
p=½ppp½,k=nαα