Liens entre problèmes de plus courts chemins, de fermeture transitive et de multiplication de matrices.

En algorithmique, pour montrer que deux problèmes sont reliés une approche courante consiste à exhiber des réductions d'un problème à l'autre. Une réduction d'un problème A à un problème B consiste à montrer que, via des transformations et des calculs, pour résoudre A je peux me ramener à résoudre B. Autrement dit, si je sais résoudre B, je peux l'utiliser pour résoudre A. Une réduction consiste parfois juste à remarquer que A est un cas particulier de B, mais parfois fait appel à des transformations plus subtiles. Cela permet d'énoncer des résultats du genre : si je sais résoudre B en temps et espace O(T(n,m)), alors je sais résoudre A en temps O(T(n,m)²+nm) et espace O(T(n,m)+n).

Ce type de liens entre problèmes est bien sûr très utilisé en théorie de la complexité. Un exemple typique est la définition de la classe des problèmes NP-complets. Ceci-dit, il est aussi très intéressant d'avoir des liens entre problèmes polynomiaux. L'objectif de ce sujet est de dresser des liens entre des problèmes importants de théorie des graphes, à savoir des problèmes de calcul de chemins, ainsi qu'avec des problèmes matriciels comme la multiplication de matrices.

Liste (non exhaustive) de problèmes à relier (si possible) :

• Plus courts chemins à partir d'un sommet source, dans un graphe orienté dont les arcs ont des poids positifs.
• Plus courts chemins entre tous les sommets, dans un graphe orienté dont les arcs ont des poids positifs.
• Plus courts chemins à partir d'un sommet source, dans un graphe orienté sans poids.
• Plus courts chemins entre tous les sommets, dans un graphe orienté sas poids.
• Fermeture transitive d'un graphe orienté (dans la fermeture x → y s'il existe un chemin de x à y dans le graphe initial)
  
• Fermeture transitive d'un graphe orienté acyclique (càd. sans circuit).
• Multiplication de deux matrices d'entiers.
• Multiplication de deux matrices booléennes.
• Fermeture transitive d'une matrice booléenne (fermeture transitive de M = V_n≥0 Mⁿ).
  

Pour chacun de ces problèmes, il sera bien sûr intéressant présenter les meilleurs complexités (temps et espace) connues à l'heure actuelle, mais on s'attachera surtout à décrire et analyser des réductions reliant ces différents problèmes.

Quelques références (pas exhaustif).

• Introduction à l'algorithmique, livre de T. Cormen, C. Leiserson, R. Rivest (et C. Stein dans la dernière version), Dunod (1994). Des informations sur tous les problèmes cités, voir par exemple les exercices 31.3.7 et 31.5.4 dans l'édition 1994 chez Dunod.
• The design and analysis of computer algorithms, livre de Aho, Hocroft et Ullman, Addison-Wesley (1974).
• Integer priority queues with decrease key in constant time and the single source shortest paths problem, article de Mikkel Thorup, Journal of Computer and System Science (2004). Lecture pas indispensable. Juste pour l'introduction culturelle qui donne un état de l'art des derniers résultats sur les plus courts chemins depuis une source dans un graphe orienté pondéré.
  

Retour à la page des sujets.