David Madore's WebLog: Interrogation des graphes

Encore un problème de maths qui m'a fait m'arracher les cheveux… Le problème qui suit me paraît particulièrement séduisant et mystifiant. Je vais tenter de l'expliquer en détails sans supposer de connaissance mathématique particulière.

On considère n points, et on appelle graphe (sous-entendu : non-orienté, sans arêtes multiples et sans arêtes-boucles) sur ces n points la donnée d'un ensemble de paires (non orientés) de points appelées arêtes du graphe : il y a donc n(n−1)/2 arêtes possibles (une pour chaque paire), et chaque graphe a entre 0 et ce nombre-là d'arêtes.

Une propriété des graphes sur les n points considérés sera un ensemble de graphes (ceux qui vérifient la propriété) qui ne change pas par permutation des sommets (isomorphisme), i.e., lorsqu'un graphe a la propriété, tout graphe obtenu en permutant simplement les sommets l'a aussi : ainsi, être connexe (= tout sommet peut être relié à n'importe quel autre par une succession d'arêtes) est une propriété, ou être le graphe complet (celui qui a toutes les arêtes possibles), mais pas avoir une arête entre le sommet 1 et le sommet 2 (parce que cela donnerait un ensemble différent de graphes si on permute le sommet 2 avec le sommet 3, disons) ; en revanche, il existe un sommet relié directement à tous les autres sommets est bien une propriété admise.

Maintenant, fixons une propriété P des graphes sur les n points (admise au sens ci-dessus), et imaginons qu'on cherche à savoir si un graphe inconnu la possède : pour cela, on a le droit d'interroger le graphe en posant des questions du type y a-t-il une arête entre les sommets x et y ? (dont la réponse sera, à chaque fois, oui ou non), éventuellement en adaptant les questions en fonction des réponses précédentes ; évidemment, si on pose toutes les n(n−1)/2 questions possibles (une pour chaque paire {x,y} de sommets), on connaît complètement le graphe, donc on sait s'il possède la propriété P (elle, elle est connue !). On dira que la complexité d'interrogation d'une propriété P est le nombre minimum de questions tel qu'en posant ce nombre de questions on soit sûr (dans le pire cas) de pouvoir déterminer si un graphe quelconque possède la propriété P ou non. Je viens d'expliquer pourquoi la complexité d'interrogation de n'importe quelle propriété P sur les graphes à n sommets est toujours au plus n(n−1)/2 : c'est la complexité maximale.

Par exemple, si P est la propriété le graphe est le graphe complet, la complexité d'interrogation est justement n(n−1)/2 : c'est évident parce, que, pour pouvoir conclure que le graphe est complet, il va bien falloir vérifier que toutes les arêtes sont dedans, ce qui ne peut pas se faire ne moins de n(n−1)/2 questions. Il en va de même d'une propriété du genre le graphe a un nombre pair d'arêtes. Attention, il ne suffit pas de voir qu'un certain algorithme ne permet pas de conclure en n(n−1)/2 questions, il faut s'assurer que tout algorithme d'interrogation du graphe doit nécessairement utiliser n(n−1)/2 questions pour pouvoir conclure sur au moins un certain graphe.

Une autre façon de présenter les choses utilise des jeux : dans ce cas, on fixe la propriété P (ainsi que n, bien sûr), et deux joueurs s'affrontent, Ques et Graf. Le joueur Ques propose deux sommets à Graf, et celui-ci doit décider s'il y a une arête ou non entre eux, puis Ques propose de nouveaux deux sommets, etc. On joue jusqu'à ce que toutes les n(n−1)/2 questions aient été posées (ce qui fixe le graphe). À un moment au cours du jeu, Ques peut faire l'annonce j'ai décidé que P est vraie ou j'ai décidé que P est fausse : bien sûr, si à la fin du jeu cette annonce est incorrecte, Ques a perdu. Il peut toujours attendre la fin des n(n−1)/2 questions pour faire l'annonce en toute sécurité, mais s'il possède une stratégie gagnante dans laquelle il fait l'annonce au bout de N questions, on dira que P a la complexité en questions au plus N.

Il existe au moins deux propriétés (inintéressantes) dont la complexité d'interrogation est strictement plus petite que n(n−1)/2, à savoir 0 : c'est la propriété trivialement vraie (celle qui est possédée par tous les graphes, par définition) et la propriété trivialement fausse (celle qui n'est possédée par aucun graphe) ; on les appellera les propriétés triviales. Le problème est : y en a-t-il d'autres (au moins pour certaines valeurs de n) ? La réponse est oui, mais, bizarrement, il est vraiment difficile d'en donner des exemples. Même si on veut simplement trouver une propriété non-triviale dont la complexité soit ne serait-ce qu'un tout petit peu inférieure à n(n−1)/2, c'est très difficile et je ne connais aucun exemple simple.

J'avais conjecturé que, pour un choix judicieux du nombre k (lié au nombre de Ramsey : en fait, le plus grand k possible tel que n soit strictement inférieur au nombre de Ramsey diagonal de k), et pour n convenable, la propriété il existe k sommets qui sont tous reliés entre eux (forment un graphe complet, également appelé clique) ou dont aucun n'est relié à aucun (forment un graphe vide, également appelé anticlique) serait de complexité strictement inférieure à la complexité maximale (l'algorithme de décision consistant à demander toutes les relations entre n−1 sommets arbitraires, chercher une (k−1)-clique ou -anticlique dedans, et, s'il n'y en a pas, répondre non, sinon, chercher à voir si le sommet restant peut compléter une (k−1)-clique ou -anticlique en k-clique ou -anticlique). En fait, je ne sais pas si ça marche : ça dépendrait de résultats de théorie de Ramsey dont je n'ai aucune idée s'ils sont vrais ou pas.

Mais on m'a donné l'exemple suivant d'une propriété qui se teste en un nombre linéaire (du genre, 3n−6 ; hum, un commentateur me fait remarquer à juste titre que c'est hautement suspect, ça, c'est peut-être plutôt en 6n+O(1)) : elle est assez cinglée. C'est : le graphe est un scorpion, à savoir : il existe trois sommets x, y et z tels que : x est relié à y et à aucun autre sommet, y est relié à x et z et à aucun autre sommet, et z est relié à tous les sommets sauf x. L'interrogation qui permet de conclure que le graphe est un scorpion, en nombre linéaire de questions, n'est pas du tout évidente !

Une conjecture de Karp affirme que toute propriété monotone (disons, qui est reste vraie en ajoutant des arêtes au graphe) et non-triviale a la complexité d'interrogation maximale, n(n−1)/2. Par exemple, le graphe est connexe ou il existe un sommet relié directement à tous les autres sont des propriétés monotones, donc, si cette conjecture est juste, elles auraient la complexité maximale. Mais même pour des propriétés aussi simples, je n'arrive pas à le prouver… (En fait, c'est encore plus embarrassant que ça : j'ai l'impression d'avoir un pipo dans ce sens, mais je n'arrive pas à me convaincre que c'est juste ou que c'est du pipo.)

Et je ne parle pas de questions du genre quel est le plus petit n pour lequel il existe une propriété non-triviale n'ayant pas la complexité maximale ? ou quelle est la plus petite complexité d'interrogation possible pour une propriété non-triviale (en fonction de n) ?…