Jack Edmonds : la révélation de la complexité ---------------------------------------------
Le mathématicien américain Jack Edmonds est né en 1934. Après ses études, il entre au National Bureau of Standards, où il travaille sur la coloration des graphes, qu’il représente au moyen de cartes et de brins. À la frontière des années 1950 et 1960, l’étude des graphes est passée du stade des « problèmes plaisants et délectables » à celui de sujet académique (voir Mathématiques discrètes et Combinatoire, Bibliothèque Tangente 39, 2009).
Claude Berge décrit la méthode des chaînes alternées pour les problèmes de couplages de cardinal maximum. Dans un fameux congrès à Calgary (Canada), il présente cet « algorithme ». Jack au milieu de la salle se lève et dit : « Claude it stinks your algorithm » (« Il pue, ton algorithme »). Jack, pour ce même problème, utilise les arbres alternés ainsi que la dualité des programmes linéaires. Ses arbres ne sont pas de tout repos, ils peuvent contenir des cycles impairs, qu’il va « shrinker » (condenser) en un point, et ainsi de suite, ce qui le conduit à un algorithme polynomial. Le mot est lâché. Dans la nuit qui précède son propre exposé, il veut généraliser son algorithme à la recherche d’un ensemble de sommets d’un graphe deux à deux disjoints et de cardinal maximum ; c’est une généralisation du problème du couplage. Il a une révélation : et s’il existait des problèmes pour lesquels il n’y a pas d’algorithme polynomial ? La complexité des algorithmes est née. Dans son article Paths, Trees and Flowers, il décrit son algorithme de couplage, puis il fait une « digression » (c’est ainsi qu’il nomme le paragraphe où il mentionne que cette notion de complexité est un vrai problème mathématique).
Edmonds est également l’initiateur des approches polyédrales, proposant la description complète du polyèdre du couplage. Il résoudra alors un très grand nombre de problèmes combinatoires polynomiaux. Le problème de la partie libre commune à deux structures de matroïdes et de cardinal maximum est un exemple à la solution particulièrement élégante…
Vašek Chvátal -------------