Test de propriété pour les ensembles indépendants

Supposons que l'on nous donne un graphe et les paramètres . Existe-t-il des plages de valeurs pour (ou est-ce faisable pour tous les ) pour lesquelles il est possible de tester si est loin d'avoir un ensemble indépendant de taille au moins dans le temps ?$G$$k,\epsilon$$k$$k$$G$$\epsilon$$k$$O(n + \text{poly}(1/\epsilon))$

Si nous utilisons la notion habituelle de -far (c'est-à-dire que tout au plus bords devraient être modifiés pour obtenir un tel ensemble), alors le problème est trivial pour . Donc$\epsilon$$\epsilon n^2$$k = O(n\sqrt{\epsilon})$

• Il semble que si est plus grand, certaines idées d'échantillonnage devraient fonctionner pour résoudre le problème. Est-ce vrai ?$k$
• Y a-t-il d'autres notions de -far (c'est-à-dire peut-être bords à la place) sous lesquelles il y a des résultats non triviaux?$\epsilon$$\epsilon |E|$

Je cherche essentiellement des références à ce stade.

Ce problème a en effet été étudié. Goldreich, Goldwasser et Ron l'ont étudié dans leur article séminal qui a lancé les tests de propriété des graphes, puis Feige, Langberg et Schechtman ont également des résultats à ce sujet dans leur article FOCS '02 "Graphs avec de minuscules nombres chromatiques vectoriels et d'énormes nombres chromatiques" .

Plus précisément, [FLS '02] montre que l'on peut distinguer les graphiques avec un ensemble indépendant de taille des graphiques loin de l'être (ce qui signifie qu'au moins bords doivent être supprimés pour créer de tels un ensemble indépendant) en choisissant un sous-graphique aléatoire induit par sommets aléatoires dans le graphique et en vérifiant si le sous-graphique aléatoire a un ensemble indépendant de taille ou ne pas. ([GGR '98] a montré une borne plus faible sur de .) [FLS '02] montre également une borne inférieure sur de .ϵ ϵ n 2 s = ˜ O ( ρ 4 / ϵ 3 ) ρ s s ˜ O ( ρ / ϵ 4 ) s Ω ( ρ 3 / ϵ 2$\rho n$$\epsilon$$\epsilon n^2$$s = \tilde{O}(\rho^4/\epsilon^3)$$\rho s$$s$$\tilde{O}(\rho/\epsilon^4)$$s$$\Omega(\rho^3/\epsilon^2)$

Une autre définition naturelle de -proche d'un ensemble indépendant consiste à changer ϵ k 2 bords. Malheureusement, avec cette définition, les tests de propriétés ne semblent pas résolubles en temps polynomial. La raison en est que personne ne sait comment trouver une clique plantée (et un ensemble similaire indépendant) de o ( $\epsilon$$\epsilon k^2$sommets dans un graphe aléatoire densommets plus rapides quen O ( log n ) temps. On peut montrer qu'un sous-graphique qui est juste un peu plus dense que la moyenne peut être utilisé pour trouver la clique plantée en temps polynomial. Cela prouve qu'il n'y a pas d'algorithme polynomial pour cette variante de votre problème pourkentrelognet$o(\sqrt{n})$$n$$n^{O(\log n)}$$k$$\log n$ .$\sqrt{n}$

Référence: Feige et Krauthgamer. Trouver et certifier une grande clique cachée dans un graphique semi-aléatoire, 1999.