Je crois qu'il existe un algorithme poly (q) connu. Ma compréhension de l'algorithme de Chudnovsky, Cornuéjols, Liu, Seymour et Vušković, "Recognizing Berge Graphs", Combinatorica 2005 , est qu'il trouve soit un trou impair, soit un antihole impair dans tout graphique non parfait en temps polynomial. Les auteurs écrivent à la page 2 de leur article que le problème de trouver des trous impairs dans les graphiques qui les contiennent reste ouvert, car les étapes 1 et 3 de leur algorithme trouvent des trous mais l'étape 2 pourrait trouver un antihole à la place. Cependant, dans le cas des graphiques Paley, si vous trouvez un antihole, multipliez simplement tous les sommets qu'il contient par un non-résidu pour le transformer en un trou impair à la place.
Alternativement, par analogie avec le graphe Rado, pour chaque k il devrait y avoir un N tel que les graphes de Paley sur N ou plusieurs sommets devraient avoir la propriété d'extension: pour tout sous-ensemble de moins de k sommets, et toute 2-coloration du sous-ensemble, il existe un autre sommet adjacent à chaque sommet d'une classe de couleurs et non adjacent à chaque sommet de l'autre classe de couleurs. Si c'est le cas, alors pour k = 5, vous pourriez construire un étrange 5 trous en un temps polynomial par étape. Peut-être que cette direction est pleine d'espoir pour un algorithme poly (log (q))? Si cela fonctionne, cela montrerait au moins qu'il y a de courts trous impairs, apparemment une condition préalable nécessaire pour les trouver rapidement.
En fait, cela ne me surprendrait pas si ce qui suit était un algorithme poly (log (q)): si q est plus petit qu'une constante fixe, recherchez la réponse, sinon construisez goulûment un impair à 5 trous en recherchant séquentiellement les nombres 0, 1, 2, 3, ... pour les sommets qui peuvent être ajoutés dans le cadre d'un 5 trous partiel. Mais peut-être que prouver qu'il fonctionne en temps poly (log (q)) nécessiterait une théorie des nombres approfondie.
D'après les résultats de Chung, Graham et Wilson, "Graphiques quasi-aléatoires", Combinatorica 1989, l'algorithme randomisé suivant résout le problème dans un nombre d'essais attendu constant lorsque q est premier: si q est suffisamment petit, recherchez la réponse, sinon, choisissez à plusieurs reprises un ensemble aléatoire de cinq sommets, vérifiez s'ils forment un trou impair, et si c'est le cas, renvoyez-le. Mais ils ne disent pas si cela fonctionne quand q n'est pas un pouvoir premier mais un pouvoir premier, alors peut-être que vous auriez besoin d'être plus prudent dans ce cas.
