Intersection de matroïdes

En optimisation combinatoire , le problème d'intersection de matroïdes consiste à trouver un ensemble commun indépendant le plus grand possible entre deux matroïdes sur le même ensemble de base. Si les éléments du matroïde sont affectés de poids réels, le problème d'intersection de matroïdes pondérés consiste à trouver un ensemble commun indépendant ayant le poids maximal possible. Ces problèmes généralisent de nombreux problèmes d'optimisation combinatoire, notamment la recherche de correspondances maximales et de correspondances de poids maximales dans les graphes bipartis et la recherche d'arborescences dans les graphes orientés .

Le théorème d'intersection de matroïdes , dû à Jack Edmonds , dit qu'il existe toujours un certificat de borne supérieure simple, consistant en un partitionnement de l'ensemble fondamental entre les deux matroïdes, dont la valeur (somme des rangs respectifs ) est égale à la taille d'un ensemble indépendant commun maximal. Sur la base de ce théorème, le problème d'intersection de matroïdes pour deux matroïdes peut être résolu en temps polynomial en utilisant des algorithmes de partitionnement de matroïdes .

Soit G = ( U , V , E ) un graphe bipartite . On peut définir un matroïde de partition M _U sur l'ensemble fondamental E , dans lequel un ensemble d'arêtes est indépendant si aucune des arêtes n'a la même extrémité dans U . De même, on peut définir un matroïde M _V dans lequel un ensemble d'arêtes est indépendant si aucune des arêtes n'a la même extrémité dans V . Tout ensemble d'arêtes qui est indépendant à la fois dans M _U et M _V a la propriété qu'aucune de ses arêtes ne partage une extrémité ; c'est-à-dire qu'il s'agit d'un appariement . Ainsi, le plus grand ensemble commun indépendant de M _U et M _V est un appariement maximal dans G .

De même, si chaque arête a un poids, alors l'ensemble indépendant du poids maximal de M _U et M _V est une correspondance de poids maximal dans G .

Il existe plusieurs algorithmes en temps polynomial pour l'intersection pondérée de matroïdes, avec différents temps d'exécution. Les temps d'exécution sont donnés en termes de - le nombre d'éléments dans l'ensemble de base commun, - le maximum entre les rangs des deux matroïdes, - le nombre d'opérations requises pour un oracle de recherche de circuit , et - le nombre d'éléments dans l'intersection (au cas où nous voudrions trouver une intersection d'une taille spécifique ).

• L'algorithme d' Edmonds utilise la programmation linéaire et les polyèdres.
• Algorithme de Lawler .
• Algorithme d'Iri et Tomizawa
• L'algorithme d' Andras Frank utilise des opérations arithmétiques.
• Algorithme d' Orlin et Vande-Vate.
• L'algorithme de Cunningham nécessite des opérations sur des matroïdes généraux et des opérations sur des matroïdes linéaires , pour deux matrices r par n .
• Brezovec, Cornuejos et Glover présentent deux algorithmes pour l'intersection de matroïdes pondérés.
  • Le premier algorithme nécessite que tous les poids soient des entiers et trouve une intersection de cardinalité dans le temps .
  • Le deuxième algorithme s'exécute dans le temps .
• Huang, Kakimura et Kamiyama montrent que le problème d'intersection de matroïdes pondérés peut être résolu en résolvant W instances du problème d'intersection de matroïdes non pondérés, où W est le plus grand poids donné, en supposant que tous les poids donnés sont entiers. Cet algorithme est plus rapide que les algorithmes précédents lorsque W est petit. Ils présentent également un algorithme d'approximation qui trouve une solution e -approximative en résolvant des instances du problème d'intersection de matroïdes non pondérés, où r est le plus petit rang des deux matroïdes d'entrée.
• Ghosh, Gurjar et Raj étudient la complexité d'exécution de l'intersection des matroïdes dans le modèle de calcul parallèle .
• Bérczi, Király, Yamaguchi et Yokoi présentent des algorithmes fortement polynomiaux pour l'intersection de matroïdes pondérés en utilisant des oracles plus restreints.

Dans une variante de l'intersection de matroïdes pondérés, appelée « (P _k ) », l'objectif est de trouver un ensemble commun indépendant ayant le poids maximum possible parmi tous ces ensembles de cardinalité k , si un tel ensemble existe. Cette variante peut également être résolue en temps polynomial.

Le problème d'intersection de matroïdes devient NP-difficile lorsque trois matroïdes sont impliqués, au lieu de seulement deux.

Une preuve de ce résultat de dureté utilise une réduction du problème du chemin hamiltonien dans les graphes orientés . Étant donné un graphe orienté G avec n sommets et des nœuds spécifiés s et t , le problème du chemin hamiltonien est le problème de déterminer s'il existe un chemin simple de longueur n − 1 qui commence à s et se termine à t . On peut supposer sans perte de généralité que s n'a pas d'arêtes entrantes et t n'a pas d'arêtes sortantes. Alors, un chemin hamiltonien existe si et seulement s'il existe un ensemble de n − 1 éléments dans l'intersection de trois matroïdes sur l'ensemble d'arêtes du graphe : deux matroïdes de partition garantissant que le degré entrant et le degré sortant de l'ensemble d'arêtes sélectionné sont tous deux au plus égaux à un, et le matroïde graphique du graphe non orienté formé en oubliant les orientations des arêtes dans G , garantissant que l'ensemble d'arêtes sélectionné n'a pas de cycles.

Un autre problème de calcul sur les matroïdes, le problème de parité des matroïdes , a été formulé par Lawler comme une généralisation courante de l'intersection des matroïdes et de la correspondance de graphes non bipartis. Cependant, bien qu'il puisse être résolu en temps polynomial pour les matroïdes linéaires , il est NP-difficile pour les autres matroïdes et nécessite un temps exponentiel dans le modèle oracle des matroïdes .

Un matroïde valué est un matroïde muni d'une fonction de valeur v sur l'ensemble de ses bases, avec la propriété d'échange suivante : pour deux bases distinctes et , si , alors il existe un élément tel que et soient des bases, et : .

Étant donné un graphe bipartite pondéré G = ( X + Y , E ) et deux matroïdes valués, l'un sur X avec un ensemble de bases B _X et une valuation v _X , et l'autre sur Y avec des bases B _Y et une valuation v _Y , le problème d'affectation indépendante valuée est le problème de trouver un M correspondant dans G , tel que M _X (le sous-ensemble de X correspondant à M ) soit une base dans B _X , M _Y soit une base dans B _Y , et sous réserve de cela, la somme est maximisée. Le problème d'intersection de matroïdes pondérés est un cas particulier dans lequel les valuations des matroïdes sont constantes, nous cherchons donc uniquement à maximiser sous réserve que M _X soit une base dans B _X et M _Y soit une base dans B _Y . Murota présente un algorithme en temps polynomial pour ce problème.