Correspondance maximale dans un graphique bipartite

Question

donné un graphique bipartite $ g= (v_1 \ tasse v_2, e) $ et un ensemble $ v '\dans (v_1 \ tasse v_2) $ .Quelle est la complexité de la recherche d'une correspondance maximale dans $ g $ qui utilise uniquement $ x $ des sommets de $ V '$ ?

Answer 1

SET $ V_I '= V_I \ CAP V' $ . Vous pouvez résoudre ceci en trouvant la correspondance maximale en utilisant au plus $ K $ sommets de $ v_1 '$ et au plus $ xk $ de $ v_2 '$ pour tous $ k \ in [0, x] $ . Cela se trouve à son tour avec un flux maximum.

Pour trouver cette correspondance maximale, nous modifions la réduction habituelle au débit maximal. Laissez $ s $ être la source et $ t $ l'évier. Laissez $ l $ et $ r $ soyez des sommets auxiliaires. Ajouter un bord de $ s $ à $ l $ avec capacité $ k $ et un bord de $ r $ to $ t $ avec capacité $ xk $ . Tous les autres bords auront une capacité 1 $ $ . Ajouter un bord de $ L $ à chaque $ x \ in v_1 '$ et de $ S $ à chaque $ x \ in v_1 \ setminus v_1 '$ . Ajoutez un bord de chaque $ y \ in v_2 '$ to $ r $ et de chaque $ Y \ in v_2 \ setminus v_2 '$ à $ T $ . Pour $ (x, y) \ in e $ , ajoutez un bord de $ x $ to $ Y $ . Maintenant, le débit maximal donne une correspondance maximale en utilisant au plus $ K $ sommets dans $ v_1 '$ et < SPAN CLASS="MATH-CONTENEUR"> $ XK $ IN $ V_2 '$ .

.

Nous pouvons donc résoudre le problème dans $ \ mathcal {o} (x \ cdot m) $ où M $ M $ est la complexité du flux maximum. Les problèmes de débit maximum sont très similaires, nous pouvons donc améliorer ce problème.

Nous pouvons augmenter ou diminuer la capacité de tout bord par 1 $ tout en maintenant le flux maximal dans $ \ mathcal { O} (| e |) $ . Calculez d'abord la correspondance maximale en utilisant aucun sommet dans $ v '$ . Ensuite, augmentez la capacité du bord de $ s $ à $ l $ par $ x $ . Ensuite, à chaque étape augmente la capacité du bord de $ r $ to $ t $ et diminue la capacité du bord de $ s $ à $ l $ tout en maintenant un débit maximal. Sortir la plus grande correspondance produite. La complexité sera $ \ mathcal {o} (| e | \ sqrt {| v |} + x \ CDOT | E |) $ Si nous utilisons DINIC pour trouver la correspondance initiale bipartite.