Qu'est-ce qu'un algorithme pour trouver une couverture minimale de sommets sur un graphe bipartite avec des sommets pondérés?

10

Je sais que pour un graphique bipartite non pondéré, je peux trouver la couverture de sommet minimale en trouvant d'abord la correspondance maximale et en la transformant en couverture de sommet en utilisant le théorème de König. Y a-t-il une modification que l'on pourrait utiliser si les nœuds sont pondérés?

ds.algorithms graph-theory Andrey Fedorov
la source
1
Bien que la solution donnée par Shiva Kintali résout votre problème, je voudrais juste ajouter une remarque rapide: le théorème de König est tout au sujet de la cardinalité. Vous pouvez ajouter des pondérations, en trouvant une correspondance bipartite maximale à coût minimal (il existe des algorithmes pour cela avec des pondérations de bord; des pondérations de noeud faciles à utiliser à la place), mais vous obtiendrez toujours la couverture minimale des sommets à coût minimal - qui pourrait ne pas être la couverture de sommet à coût min (c.-à-d. qui pourrait comprendre plus de nœuds) Une correspondance min-coût sans contraintes / optimisation de cardinalité serait juste vide (pour les poids positifs)…
Magnus Lie Hetland

Réponses:

18

Le problème de la couverture des sommets pondérés peut être formulé comme un programme entier (voir http://en.wikipedia.org/wiki/Vertex_cover ). Lorsque le graphe d'entrée est bipartite, la matrice de contraintes de cette IP est totalement unimodulaire. Par conséquent, cette IP peut être résolue en temps polynomial.

Pour plus de détails sur les matrices unimodulaires totales et les algorithmes correspondants, voir l'excellent livre (trois volumes) d' Alexander Schrijver .

Shiva Kintali
la source
6
Pour être plus précis, l'IP peut être résolu en résolvant simplement la relaxation LP. De plus, on peut remarquer que le dual du LP est une généralisation de l'appariement (avec des capacités correspondant aux poids des sommets dans l'instance de couverture de vertex) et peut être résolu en réduisant le débit maximum de la manière habituelle.
Chandra Chekuri
@ChandraChekuri peudo-code de la réduction de débit maximale peut être trouvé dans la figure 4 dans le calcul incrémentiel des enveloppes de ressources dans les modèles producteur-consommateur
xuhdev