Eigenschaftsprüfung für unabhängige Mengen

9

Angenommen, wir erhalten einen Graphen und die Parameter . Gibt es Bereiche von Werten für (oder ist es für alle machbar ) , für die es möglich ist , ob ist -Far von einer unabhängigen Satz von Größe mindestens mit in der Zeit ?k , ε k k G ε k O ( n + Poly ( 1 / ε ) ) ,Gk,ϵkkGϵkO(n+poly(1/ϵ))

Wenn wir den üblichen Begriff von -far verwenden (dh höchstens Kanten müssten geändert werden, um eine solche Menge zu erhalten), dann ist das Problem für trivial . Soϵ n 2 k = O ( n ϵϵn2k=O(nϵ)

  • Es scheint, dass wenn größer ist, einige Stichprobenideen funktionieren sollten, um das Problem zu lösen. Ist das wahr ?k
  • Gibt es andere Begriffe von -far (dh vielleicht Kanten stattdessen), unter denen es nicht triviale Ergebnisse gibt?ϵ | E |ϵϵ|E|

Grundsätzlich suche ich an dieser Stelle nach Referenzen.

Suresh Venkat
quelle

Antworten:

10

Dieses Problem wurde tatsächlich untersucht. Goldreich, Goldwasser und Ron haben es in ihrem wegweisenden Artikel untersucht, der die Prüfung der Eigenschaften von Graphen eingeleitet hat, und Feige, Langberg und Schechtman haben dann auch Ergebnisse in ihrem FOCS '02 -Papier "Graphen mit winzigen chromatischen Vektorzahlen und riesigen chromatischen Zahlen". .

Insbesondere zeigt [FLS '02], dass man zwischen Graphen mit einem unabhängigen Satz von Größe von Graphen weit davon entfernt (dies bedeutet, dass mindestens Kanten entfernt werden müssen, um solche zu erzeugen eine unabhängige Menge) durch Auswahl eines zufälligen Untergraphen, der durch zufällige Eckpunkte im Diagramm induziert wird, und durch Überprüfen, ob der zufällige Untergraph eine unabhängige Menge von Größe oder hat nicht. ([GGR '98] zeigte eine schwächere Grenze für von .) [FLS '02] zeigte auch eine niedrigere Grenze für von .ε ε n 2 s = ~ O ( ρ 4 / ε 3 ) ρ s s ~ O ( ρ / ε 4 ) s Ω ( ρ 3 / ε 2 )ρnϵϵn2s=O~(ρ4/ϵ3)ρssO~(ρ/ϵ4)sΩ(ρ3/ϵ2)

Arnab
quelle
6

Eine andere natürliche Definition von -close zu einer unabhängigen Menge ist das Ändern von Kanten. Leider scheint das Testen von Eigenschaften mit dieser Definition nicht polynomiell lösbar zu sein. Der Grund ist, dass niemand weiß, wie man eine gepflanzte Clique (und eine ähnlich unabhängige Menge) von Eckpunkten in einem zufälligen Graphen von Eckpunkten schneller als Zeit findet. Man kann zeigen, dass ein Teilgraph, der nur ein bisschen dichter als der Durchschnitt ist, verwendet werden kann, um die gepflanzte Clique in Polynomzeit zu finden. Dies ist ein Beweis dafür, dass es für diese Variante Ihres Problems für einen polynomiellen Zeitalgorithmus zwischen und .ϵ k 2 o ( ϵϵk2nn O ( log n ) klogno(n)nnO(logn)klognn

Referenz: Feige und Krauthgamer. Finden und Zertifizieren einer großen versteckten Clique in einem zufälligen Diagramm, 1999.

Warren Schudy
quelle