Conjecture d'Aanderaa-Karp-Rosenberg

En informatique théorique, la conjecture d'Aanderaa-Karp-Rosenberg (aussi connue sous le nom de conjecture d'Aanderaa-Rosenberg ou conjecture de l'évasion) est un ensemble de conjectures concernant le nombre de questions de la forme « existe-t-il une arête entre le sommet $u$ et sommet $v$ ? » dans un graphe auxquelles il faut répondre pour déterminer si oui ou non un graphe non orienté possède une propriété donnée telle que la planarité ou le caractère biparti . Elles portent les noms de Stål Aanderaa, Richard M. Karp et Arnold L. Rosenberg. La conjecture affirme que, pour une large classe de propriétés, tout algorithme pour déterminer si un graphe possède une de ces propriétés, aussi élaboré soit-il, peut être amené à examiner toute paire de sommets avant de donner sa réponse. Une propriété satisfaisant cette conjecture est dite évasive.

Description

La conjecture d'Aanderaa-Rosenberg stipule que tout algorithme déterministe doit tester, dans le pire des cas, au moins une fraction constante de toutes les paires de sommets, pour déterminer une propriété de graphe monotone non triviale ; dans ce contexte, une propriété est dite monotone si elle reste vraie lorsque des arêtes sont ajoutées ; ainsi;, la planarité n'est pas monotone, mais la non-planarité est monotone. Une version plus forte de cette conjecture, appelée la conjecture d'évitement ou conjecture d'Aanderaa-Karp-Rosenberg, stipule qu'exactement $n(n-1)/2$ tests sont nécessaires. Des versions du problème pour les algorithmes randomisés et les algorithmes quantiques ont également été formulées et étudiées.

La conjecture déterministe d'Aanderaa–Rosenberg a été prouvée par Rivest & Vuillemin (1975), mais la conjecture plus forte d'Aanderaa–Karp–Rosenberg est encore non résolue. De plus, il existe un grand écart entre la borne inférieure conjecturée et la borne inférieure prouvée pour la complexité des requêtes aléatoires et quantiques.

Un exemple

La propriété d'être non vide, c'est-à-dire d'avoir au moins une arête, est une propriété monotone, car l'ajout d'une autre arête à un graphe non vide produit un autre graphe non vide. Il existe un algorithme simple pour tester si un graphe est non vide : on parcourt toutes les paires de sommets, et on teste si une paire est connectée par une arête. Si on trouve une arête, le graphe n'est pas vide, et si le parcours se termine sans avoir trouvé d'arêtes, le graphe est vide. Pour certains graphes, comme les graphes complets, cet algorithme se termine rapidement, sans avoir à tester chaque paire de sommets, mais sur le graphe vide, il faut tester toutes les paires possibles avant de pouvoir conclure. Par conséquent, la complexité de cet algorithme est en $n(n-1)/2$ , car dans le pire des cas, l'algorithme doit effectuer $n(n-1)/2$ essais.

L'algorithme ci-dessus n'est pas la seule méthode possible pour tester si un graphe n'est pas vide, mais la conjecture d'Aanderaa-Karp-Rosenberg dit que tout algorithme déterministe pour tester qu'un graphe n'est pas vide la même complexité de requêtes dans le pire des cas, à savoir $n(n-1)/2$. Autrement dit, la propriété d'être non vide est évasive. Pour cette propriété, le résultat est facile à prouver directement : si un algorithme n'effectue pas $n(n-1)/2$ tests, il ne peut pas distinguer le graphe vide d'un graphe qui a une arête reliant l'une des paires de sommets non testés, et il donne donc une réponse incorrecte sur l'un de ces deux graphes.

Définitions

Formellement, une propriété de graphe est une fonction de la famille de tous les graphes dans l'ensemble $\{0,1\}$ telle que deux graphes isomorphes ont la même valeur. Par exemple, la propriété de contenir au moins un sommet de degré deux est une telle propriété de graphe, mais la propriété que le premier des sommets est de degré deux ne l'est pas, car elle dépend de l'étiquetage du graphe (en particulier, cela dépend de quel sommet est le « premier » sommet). Une propriété de graphe est dite non triviale si elle n'attribue pas la même valeur à tous les graphes. Par exemple, la propriété d'être vide n'est pas triviale, car le graphe vide possède cette propriété, mais pas les graphes non vides. Une propriété de graphe est dite monotone si l'ajout d'arêtes ne modifie pas la propriété. Par exemple, la propriété d'être non planaire est monotone : un supergraphe (qui contient plus d'arêtes) d'un graphe non planaire est lui-même non planaire. En revanche, la propriété d'être un graphe régulier n'est pas monotone.

Complexité des requêtes

La complexité déterministe d'une requête d'évaluation d'une fonction à $n$ bits étiquetés $x_{1},x_{2},\dots x_{n}$ est le nombre de bits $x_{i}$ qui doivent être lus, dans le pire des cas, par un algorithme déterministe qui évalue la fonction. Par exemple, si la fonction prend la valeur 0 lorsque tous les bits sont égaux à 0 et prend la valeur 1 sinon (comme la disjonction logique), alors sa complexité de requête déterministe est exactement $n$ : en effet, dans le pire des cas, et quel que soit l'ordre dans lequel on examine les entrées, il se peut que les $n-1$ premier bits soient égaux à 0, et la valeur de la fonction dépend alors du dernier bit. Si un algorithme ne lit pas ce bit, la réponse peut être incorrecte (de tels arguments sont appelés arguments de l'adversaire).

La complexité randomisée d'évaluation d'une fonction est définie de manière similaire, sauf que l'algorithme peut être randomisé. En d'autres termes, on peut lancer un dé et utiliser le résultat de ces lancers pour décider quels bits interroger et dans quel ordre. Cependant, l'algorithme randomisé doit toujours produire la bonne réponse pour toutes les entrées. Ces algorithmes sont les algorithmes de Las Vegas ; les algorithmes de Monte Carlo, sont autorisés à faire des erreurs. La complexité des requêtes aléatoire peut être définie pour les algorithmes de Las Vegas et de Monte Carlo, mais la version aléatoire de la conjecture d'Aanderaa-Karp-Rosenberg concerne la complexité des requêtes à la Las Vegas.

La complexité des requêtes quantiques est la généralisation naturelle de la complexité des requêtes aléatoires, permettant des requêtes et des réponses quantiques. La complexité des requêtes quantiques peut aussi bien être définie pour les algorithmes de Monte Carlo ou algorithmes de Las Vegas.

Dans le contexte de la conjecture d'Aanderaa-Karp-Rosenberg, la fonction à évaluer est une propriété de graphe, et l'entrée peut être vue comme une chaîne binaire de taille $n(n-1)/2$, décrivant pour chaque paire de sommets s'il existe ou non une arête avec cette paire comme extrémités. La complexité de la requête de toute fonction sur cette entrée est au plus $n(n-1)/2$, car un algorithme qui fait les $n(n-1)/2$ requêtes peut lire l'intégralité de l'entrée et déterminer complètement le graphe d'entrée.

Complexité déterministe des requêtes

Pour les algorithmes déterministes, Rosenberg (1973) a conjecturé que pour toutes les propriétés de graphe non triviales sur $n$ sommets, décider si un graphe possède cette propriété a une complexité en $\Omega (n^{2})$. La condition de non-trivialité est requise pour éviter des questions triviales telles que « est-ce un graphe ? » auxquelles on peut répondre sans même poser une question.

Un graphe scorpion. L'un des trois sommets rouges du chemin est adjacent à tous les autres sommets et les deux autres sommets rouges n'ont pas d'autres adjacences.

La conjecture a été réfutée par Aanderaa, qui a présenté une propriété de graphe orienté (la propriété de « posséder un sommet puits ») qui ne nécessitait que $O(n)$ requêtes à tester. Dans ce contexte, un puits dans un graphe orienté est un sommet de degrée entrant $n-1$ et de degré sortant nul. L'existence d'un puits peut être testée en moins de $3n$ requêtes. Une autre propriété de graphes non orientés qui peut également être testée en $O(n)$ requêtes est la propriété d'être un graphe scorpion, propriété décrite pour la première fois dans Best, van Emde Boas & Lenstra (1974). Un graphe scorpion est un graphe contenant un chemin à trois sommets, de sorte qu'une extrémité du chemin est connectée à tous les sommets restants, tandis que les deux autres sommets du chemin n'ont pas d'arêtes incidentes autres que celles du chemin.

Aanderaa et Rosenberg ont ensuite formulé une nouvelle conjecture (dite la conjecture d'Aanderaa-Rosenberg ) qui affirme que décider si un graphe possède une propriété de graphe monotone non triviale nécessite $\Omega (n^{2})$ requêtes. Cette conjecture a été résolue positivement par Rivest & Vuillemin (1975) qui montrent qu'au moins ${\tfrac {1}{16}}n^{2}$ requêtes sont nécessaires pour tester toute propriété de graphe monotone non triviale. La borne a été améliorée en ${\tfrac {1}{9}}n^{2}$ par Kleitman & Kwiatkowski (1980), puis en ${\bigl (}{\tfrac {1}{4}}-\varepsilon {\bigr )}n^{2}$ (pour toute $\varepsilon >0$ ) par Kahn, Saks & Sturtevant (1984), en ${\bigl (}{\tfrac {8}{25}}-\varepsilon {\bigr )}n^{2}$ par Korneffel & Triesch (2010), et en${\bigl (}{\tfrac {1}{3}}-\varepsilon {\bigr )}n^{2}$ par Scheidweiler & Triesch (2013).

Richard Karp a énoncé une conjecture la plus forte, appelée la conjecture d'évitement ou la conjecture d'Aanderaa-Karp-Rosenberg, selon laquelle « toute propriété de graphe monotone non triviale pour les graphes sur $n$ sommets est évasive ». Une propriété est dite évasive si déterminer qu'un graphe donné possède cette propriété peut nécessiter toutes les $n(n-1)/2$ requêtes possibles. Cette conjecture dit que le meilleur algorithme pour tester une propriété monotone non triviale doit (dans le pire des cas) interroger toutes les arêtes possibles. Cette conjecture est encore ouverte, bien que plusieurs propriétés spéciales de graphes se soient révélées évasives pour tous $n$. La conjecture est démontrée dans le cas où $n$ est une puissance première par Kahn, Saks & Sturtevant (1984) en utilisant une approche topologique. La conjecture a également été prouvée pour toutes les propriétés monotones non triviales sur les graphes bipartis par Yao (1988) . Il a également été démontré que les propriétés fermées par passage aux mineurs sont évasives pour les grandes valeurs de $n$.

Dans l'article de Kahn, Saks & Sturtevant (1984), la conjecture a également été généralisée aux propriétés de fonctions autres que celles portant sur les graphes, en supposant que toute fonction monotone non triviale faiblement symétrique est évasive. Ce cas est également résolu lorsque $n$ est une puissance primordiale par Lovász & Young (2002).

Complexité des requêtes randomisées

Richard Karp a également conjecturé que $\Omega (n^{2})$ requêtes sont nécessaires pour tester des propriétés monotones non triviales même si des algorithmes randomisés sont autorisés. Aucune propriété monotone non triviale n'est connue qui nécessite moins de ${\tfrac {1}{4}}n^{2}$ requêtes. Une borne inférieure linéaire (c'est-à-dire en $\Omega (n)$) sur toutes les propriétés monotones découle d'une relation très générale entre les complexités des requêtes randomisées et déterministes. La première borne inférieure super-linéaire pour toutes les propriétés monotones a été donnée par Yao (1991) qui a montré que $\Omega {\bigl (}n(\log n)^{1/12}{\bigr )}$ requêtes sont nécessaires. Cette borne a été améliorée par King (1991) en $\Omega (n^{5/4})$, puis par Hajnal (1991) à $\Omega (n^{4/3})$. La meilleure borne inférieure connue en 2007 (parmi les bornes valables pour toutes les propriétés monotones) est $\Omega {\bigl (}n^{4/3}(\log n)^{1/3}{\bigr )}$, donnée par Chakrabarti & Khot (2007).

Certains résultats donnent des bornes inférieures qui sont déterminées par ce qui est appelé la probabilité critique $p$ de la propriété de graphe monotone considérée. La probabilité critique $p$ est définie comme étant le nombre unique $p$ dans l'intervalle $[0,1]$ tel qu'un graphe aléatoire $G(n,p)$, obtenu en choisissant aléatoirement si chaque arête existe, indépendamment des autres arêtes, avec probabilité $p$ par arête, possède cette propriété avec une probabilité égale à ${\tfrac {1}{2}}$. Friedgut, Kahn & Wigderson (2002) ont montré que toute propriété monotone avec probabilité critique $p$ requiert

$\Omega \left(\min \left\{{\frac {n}{\min(p,1-p)}},{\frac {n^{2}}{\log n}}\right\}\right)$

requêtes. Pour le même problème, O'Donnell et al. (2005) ont montré une borne inférieure en $\Omega (n^{4/3}/p^{1/3})$ .

Comme dans le cas déterministe, il existe de nombreuses propriétés particulières pour lesquelles une borne inférieure en $\Omega (n^{2})$ est connue. De plus, des bornes inférieures meilleures sont connues pour plusieurs classes de propriétés de graphe. Par exemple, pour tester si le graphe a un sous-graphe isomorphe à un graphe donné (le problème de l'isomorphisme de sous-graphe), la meilleure borne inférieure connue est $\Omega (n^{3/2})$ , due à Gröger (1992).

Complexité des requêtes quantiques

Pour la complexité des requêtes quantiques à erreur bornée, la meilleure borne inférieure connue est $\Omega {\bigl (}n^{2/3}(\log n)^{1/6}{\bigr )}$, comme l'a observé Andrew Yao. Elle est obtenue en combinant la borne inférieure randomisée avec la méthode de l'adversaire quantique. La meilleure borne inférieure possible que l'on puisse espérer atteindre est $\Omega (n)$, contrairement au cas classique, grâce à l'algorithme de Grover qui donne une algorithme en $O(n)$ requêtes pour tester la propriété monotone d'être une graphe non vide. Comme dans le cas déterministe et randomisé, certaines propriétés sont connues pour avoir une borne inférieure en $\Omega (n)$, par exemple d'être non vide (ce qui découle de l'optimalité de l'algorithme de Grover) et la propriété de contenir un triangle. Certaines propriétés de graphes sont connues pour avoir une borne inférieure en $\Omega (n^{3/2})$, et même certaines propriétés avec une borne inférieure en $\Omega (n^{2})$. Par exemple, la propriété monotone de la non planarité nécessite $\Theta (n^{3/2})$ requêtes et la propriété monotone de contenir plus de la moitié du nombre possible d'arêtes (également appelée la fonction majoritaire) nécessite $\Theta (n^{2})$ requêtes .

Notes et références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Aanderaa–Karp–Rosenberg conjecture » (voir la liste des auteurs).

Bibliographie complémentaire

• Béla Bollobás, Extremal Graph Theory, New York, Dover Publications, 2004 (ISBN 978-0-486-43596-1), « Chapter VIII. Complexity and packing », p. 401–437.
• László Lovász et Neal E. Young, « Lecture Notes on Evasiveness of Graph Properties », Arxiv,‎ 2002 (arXiv cs/0205031)
• Michael Saks, « Decision Trees: Problems and Results, Old and New »
• Lipton, Richard J. et Regan, Kenneth W., People, problems, and proofs. : Essays from Gödel’s lost letter: 2010, Berlin, Springer, 2013, xviii + 333 (ISBN 978-3-642-41421-3, zbMATH 1305.68025).
• Tamás Csernák et Lajos Soukup, « Elusive properties of infinite graphs », Arxiv,‎ 2021 (arXiv 2112.14689).
• Scott Aaronson, Shalev Ben-David, Robin Kothari et Avishay Tal, « Quantum Implications of Huang's Sensitivity Theorem », Arxiv,‎ 2020 (arXiv 2004.13231).
• SDishant Goyal, Varunkumar Jayapaul et Venkatesh Raman, « Elusiveness of finding degrees », Discrete Applied Mathematics, vol. 286,‎ 2020, p. 128-139.