Correspondance de cardinalité maximale - Maximum cardinality matching

La correspondance de cardinalité maximale est un problème fondamental de la théorie des graphes . On nous donne un graphe , et le but est de trouver une correspondance contenant autant d'arêtes que possible, c'est-à-dire un sous-ensemble de cardinalité maximale des arêtes tel que chaque sommet soit adjacent à au plus une arête du sous-ensemble. Comme chaque arête couvrira exactement deux sommets, ce problème équivaut à la tâche de trouver une correspondance qui couvre autant de sommets que possible. ${\style d'affichage G}$

Un cas particulier important du problème de correspondance de cardinalité maximale est lorsque G est un graphe bipartite , dont les sommets V sont partitionnés entre les sommets gauches de X et les sommets droits de Y , et les arêtes de E connectent toujours un sommet gauche à un sommet droit. Dans ce cas, le problème peut être résolu efficacement avec des algorithmes plus simples que dans le cas général.

Algorithmes pour les graphes bipartites

La façon la plus simple de calculer une correspondance de cardinalité maximale est de suivre l' algorithme de Ford-Fulkerson . Cet algorithme résout le problème plus général du calcul du flux maximal , mais peut être facilement adapté : nous transformons simplement le graphe en un réseau de flux en ajoutant un sommet source au graphe ayant une arête à tous les sommets gauches de X , en ajoutant un sommet puits ayant une arête à partir de tous les sommets droits de Y , gardant toutes les arêtes entre X et Y , et donnant une capacité de 1 à chaque arête. L'algorithme de Ford-Fulkerson procédera ensuite en trouvant à plusieurs reprises un chemin croissant d'un certain x ∈ X à un certain y ∈ Y et en mettant à jour l'appariement M en prenant la différence symétrique de ce chemin avec M (en supposant qu'un tel chemin existe). Comme chaque chemin peut être trouvé dans le temps, le temps d'exécution est , et la correspondance maximale consiste en les arêtes de E qui transportent le flux de X à Y . ${\style d'affichage \ O(E)}$${\style d'affichage \ O(VE)}$

Une amélioration de cet algorithme est apportée par l'algorithme plus élaboré de Hopcroft-Karp , qui recherche simultanément plusieurs chemins d'augmentation. Cet algorithme s'exécute dans le temps. ${\style d'affichage O({\sqrt {V}}E)}$

L'algorithme de Chandran et Hochbaum pour les graphes bipartites s'exécute dans un temps qui dépend de la taille de la correspondance maximale , qui pour est . En utilisant des opérations booléennes sur des mots de taille, la complexité est encore améliorée à . ${\style d'affichage k}$${\style d'affichage |X|<|Y|}$${\displaystyle O\left(\min\{|X|k,E\}+{\sqrt {k}}\min\{k^{2},E\}\right)}$${\style d'affichage \lambda }$${\displaystyle O\left(\min \left\{|X|k,{\frac {|X||Y|}{\lambda }},E\right\}+k^{2}+{\frac {k^{2.5}}{\lambda }}\right)}$

Des algorithmes plus efficaces existent pour des types particuliers de graphes bipartis :

• Pour les graphes bipartis clairsemés , le problème d'appariement maximal peut être résolu avec l'algorithme de Madry basé sur les flux électriques.${\displaystyle {\tilde {O}}(E^{10/7})}$
• Pour planes graphes bipartites, le problème peut être résolu dans le temps , où n est le nombre de sommets, en réduisant le problème de débit maximal avec de multiples sources et des puits.${\displaystyle O(n\log ^{3}n)}$

Algorithmes pour les graphes arbitraires

L' algorithme de bloom trouve une correspondance de cardinalité maximale dans les graphiques généraux (pas nécessairement bipartites). Il court dans le temps . Une meilleure performance de O ( √ V E ) pour les graphes généraux, correspondant à la performance de l' algorithme de Hopcroft-Karp sur les graphes bipartites, peut être obtenue avec l'algorithme beaucoup plus compliqué de Micali et Vazirani. La même borne a été obtenue par un algorithme de Blum ( de ) et un algorithme de Gabow et Tarjan . ${\displaystyle O(|V|^{2}\cdot |E|)}$

Une approche alternative utilise la randomisation et est basée sur l' algorithme de multiplication matricielle rapide. Cela donne un algorithme aléatoire pour les graphes généraux avec complexité . C'est mieux en théorie pour des graphes suffisamment denses , mais en pratique l'algorithme est plus lent. ${\style d'affichage O(V^{2.376})}$

D'autres algorithmes pour la tâche sont examinés par Duan et Pettie (voir le tableau I). En termes d' algorithmes d'approximation , ils soulignent également que l' algorithme de bloom et les algorithmes de Micali et Vazirani peuvent être considérés comme des algorithmes d'approximation fonctionnant en temps linéaire pour toute borne d'erreur fixe.

Applications et généralisations

• En trouvant un appariement de cardinalité maximale, il est possible de décider s'il existe un appariement parfait .
• Le problème de trouver un appariement avec un poids maximum dans un graphique pondéré est appelé problème d'appariement de poids maximum , et sa restriction aux graphiques bipartites est appelé problème d'affectation . Si chaque sommet peut être associé à plusieurs sommets à la fois, il s'agit alors d'un problème d'affectation généralisé .
• Une correspondance de priorité est une correspondance de cardinalité maximale particulière dans laquelle les sommets prioritaires sont appariés en premier.
• Le problème de trouver une correspondance de cardinalité maximale dans un hypergraphe est NP-complet même pour les hypergraphes 3-uniformes.

Les références