Clique plantée - Planted clique
Dans la théorie de la complexité de calcul , une clique plantée ou une clique cachée dans un graphe non dirigé est une clique formée à partir d'un autre graphe en sélectionnant un sous-ensemble de sommets et en ajoutant des arêtes entre chaque paire de sommets du sous-ensemble. Le problème de la clique plantée est le problème algorithmique consistant à distinguer les graphes aléatoires des graphiques qui ont une clique implantée. Ceci est une variante du problème de la clique ; il peut être résolu en temps quasi-polynomial mais on suppose qu'il ne peut pas être résolu en temps polynomial pour des valeurs intermédiaires de la taille de la clique. La conjecture selon laquelle aucune solution de temps polynomiale n'existe est appelée la conjecture de clique plantée ; il a été utilisé comme hypothèse de dureté de calcul .
Définition
Une clique dans un graphe est un sous-ensemble de sommets, tous adjacents les uns aux autres. Une clique plantée est une clique créée à partir d'un autre graphique en ajoutant des arêtes entre toutes les paires d'un sous-ensemble sélectionné de sommets.
Le problème de la clique plantée peut être formalisé comme un problème de décision sur une distribution aléatoire sur des graphes, paramétré par deux nombres, n (le nombre de sommets) et k (la taille de la clique). Ces paramètres peuvent être utilisés pour générer un graphique, par le processus aléatoire suivant:
- Créez un graphe aléatoire Erdős – Rényi sur n sommets en choisissant indépendamment pour chaque paire de sommets s'il faut inclure une arête reliant cette paire, avec une probabilité de 1/2 pour chaque paire.
- Décidez si vous souhaitez ou non ajouter une clique au graphique, avec une probabilité 1/2; sinon, retournez le graphique formé à l'étape 1.
- Choisissez au hasard un sous-ensemble de k des n sommets et ajoutez une arête (si elle n'est pas déjà présente) entre chaque paire de sommets sélectionnés.
Le problème est alors de déterminer de manière algorithmique si l'un des graphes issus de ce processus contient une clique d'au moins k sommets.
Avec une probabilité élevée, la taille de la plus grande clique dans un graphe aléatoire à n -vertex est proche de 2 log 2 n . Et lorsque k est plus grand que la racine carrée de n , les sommets d'une clique plantée peuvent être reconnus comme ayant des degrés inhabituellement élevés , ce qui facilite la recherche d'une clique plantée. Par conséquent, la plage de valeurs la plus intéressante pour le paramètre k se situe entre ces deux valeurs,
Algorithmes
Grandes cliques
Pour des valeurs suffisamment grandes du paramètre k , le problème de la clique plantée peut être résolu (avec une probabilité élevée) en temps polynomial.
Kučera (1995) observe que, alors que presque sûrement tous les sommets de la clique plantée ont un degré plus élevé que tous les sommets en dehors de la clique, ce qui rend la clique très facile à trouver. Il décrit une modification du processus aléatoire de génération d'instances de cliques plantées, qui rend les degrés de sommet plus uniformes même pour de grandes valeurs de k , mais montre que malgré cette modification, la clique plantée peut encore être trouvée rapidement.
Alon, Krivelevich & Sudakov (1998) prouvent qu'une clique plantée peut être trouvée avec une forte probabilité par la méthode suivante:
- Calculez le vecteur propre de la matrice de contiguïté correspondant à sa deuxième valeur propre la plus élevée .
- Sélectionnez les k sommets dont les coordonnées dans ce vecteur propre ont les plus grandes valeurs absolues .
- Renvoie l'ensemble des sommets adjacents à au moins 3/4 des sommets sélectionnés.
Ils montrent comment modifier cette technique pour qu'elle continue de fonctionner chaque fois que k est au moins proportionnel à un multiple de la racine carrée du nombre de sommets. De grandes cliques plantées peuvent également être trouvées en utilisant la programmation semi-définie . Une technique combinatoire basée sur l'échantillonnage aléatoire de sommets peut atteindre la même borne sur k et s'exécute en temps linéaire .
Temps quasi-polynomial
Il est également possible de résoudre le problème de la clique plantée, quel que soit le choix de k , en temps quasi-polynomial . Étant donné que la plus grande clique dans un graphique aléatoire a généralement une taille proche de 2 log 2 n , une clique plantée de taille k (si elle existe) peut être trouvée avec une probabilité élevée par la méthode suivante:
- Boucle à travers tous les ensembles S de sommets.
- Pour chaque choix de S , testez si S est une clique. Si elle est, et , de retour S . Dans le cas contraire, trouver l'ensemble T de sommets qui sont adjacents à tous les sommets S . Si , de retour T .
Le temps d'exécution de cet algorithme est quasipolynomial, car il y a quasipolynomialement de nombreux choix de S sur lesquels boucler. Cette méthode est garantie d'essayer un ensemble S qui est un sous-ensemble de la clique plantée; avec une forte probabilité, l'ensemble T ne sera constitué que d'autres membres de la clique plantée.
Comme hypothèse de dureté
La conjecture de la clique plantée est la conjecture qu'il n'y a pas d'algorithme de temps polynomial qui prend comme entrée les graphiques produits par le processus de clique plantée et distingue ceux avec des cliques plantées de ceux qui n'ont pas planté de cliques avec une probabilité significativement meilleure que le hasard.
Hazan et Krauthgamer (2011) ont utilisé l'hypothèse selon laquelle trouver des cliques plantées est difficile comme hypothèse de dureté de calcul pour prouver que, si tel est le cas, il est également difficile de se rapprocher du meilleur équilibre de Nash dans une partie à deux joueurs. La conjecture de clique plantée a également été utilisée comme hypothèse de dureté pour montrer la difficulté de tester la propriété k -indépendance des distributions aléatoires, de trouver des clusters dans les réseaux sociaux et de l'apprentissage automatique .