Ensembles saturés dans un graphique bipartite

Question

let $ g= (x \ tasse y, e) $ être un graphique bipartite non pondéré. On nous donne que pour chaque $ W \ subseteq X $ il soutient que $ | W | \ leq | N (W) | $ , où $ N (W) $ neighborhod de $ W $ in $ y $ (condition de mariage de la salle aka).

Mon but est de trouver un sous-ensemble $ W ^ * \ subseteq X $ avec $ | W ^ * |= | N (w ^ *) | $ si un tel sous-ensemble existe (évidemment, il n'est pas nécessaire d'exister). Depuis que je ne suis pas au courant d'un nom officiel de cette propriété, je réfère à un tel $ W ^ * $ comme ensemble saturé .

questions:

1. Est-ce que cette propriété est largement connue? A-t-il un nom différent?
2. En supposant que la condition de mariage est titulaire, il est simple de montrer que chaque union d'ensembles saturés est également saturé. Un problème intéressant est de trouver l'ensemble maximum saturé. Je décris ci-dessous une solution quelque peu naïve avec l'exécution $ O (| V | \ cdot | E |) $ , mais je pense qu'il peut être résolu encore plus vite. Aucune idée?
3. prétendument, un problème faiblement plus facile est de trouver un ensemble saturé , pas nécessairement le maximum (à nouveau, en supposant que la condition de mariage contient). Pouvons-nous résoudre ce problème plus rapidement que $ O (| V | \ CDOT | E |) $ ?

---

edit: Voici un croquis pour l'algorithme que j'ai mentionné ci-dessus: supposons que l'état du mariage est contenant pour $ g $ . Ensuite, comme dit, avec un travail de théorie des bits, nous pouvons montrer que

lemme: laissez $ g $ être un graphique bipartite satisfaisant la condition de mariage. Ensuite, chaque union des ensembles saturés est également saturé.

Le lemme suggère qu'il existe un ensemble unique maximum saturé. La question peut donc être indiquée différemment:

Étant donné un nœud $ x \ X $ , déterminer si elle participe à un ensemble saturé ou non .

Si la réponse est oui, elle participe également à l'ensemble maximum saturé. Le pseudo algorithme se passe comme suit:

1. Exécuter algorithme de Hopcroft-Karp pour trouver une correspondance maximale $ M $ qui couvre $ X $ $ O ( \ sqrt {| v |} | e |) $ temps. Une telle correspondance existe en raison de la condition de mariage.
2. pour chaque nœud $ x \ in x $ ,
   • ajouter temporairement un noeud $ x '$ $ X $ , qui est relié à tous les voisins de $ x $ . Appelez le graphique que nous obtenons $ g_x $ .
   • Notez que $ M $ est une correspondance partielle de $ G_x $ qui est presque maximale (jusqu'à à un bord); ainsi, nous pouvons trouver une correspondance maximale $ m_x $ pour $ G_x $ en trouvant un chemin augmentant dans < span class="math-conteneur"> $ G_x $ , dans O $ (| V | + | E |) $ temps (mêmes détails que dans Hopcroft-Karp).
   • si $ | m | <| m_x |, $ continuer. Sinon, si $ | M |= | m_x | $ , ajoutez $ x $ pour l'ensemble renvoyé.

L'analyse provient des premiers principes. S'il existe un ensemble saturé $ W \ subseteq X $ avec $ x \ in W $ , à savoir, $ | w |= | n_g (w) | $ alors $$ | W \ tasse \ {x '\} |= | w | +1= | n_g (w) | + 1= | n_ {g_x} (w) | +1, $$ si $ W \ cup \ {x \} $ constitue une violation de la condition de mariage $ G_x $ . Par conséquent, $ | m |= | m_x | $ . On peut par analogie montrer que si $ x $ ne participe pas à un ensemble saturé, puis $ | m_x |= | M | +1 $ .

Answer 1

Fixez une correspondance maximale $ M $ . Laissez $ z \ subteteq y $ être l'ensemble des nœuds qui ne correspondent pas à des nœuds dans $ x . Nous pouvons voir un nœud $ x \ in x $ appartient à un ensemble saturé si et seulement s'il n'existe pas un chemin alternatif de $ x $ à un nœud dans $ z $ , c'est-à-dire un chemin $ xy_1x_1 \ cdots y_kx_kz $ où $ (x_i, y_i) \ in m $ et $ z \ in z $ (La preuve est similaire à la preuve exacte de votre algorithme).

Vous pouvez donc ajouter des instructions à tous les bords dans $ e $ telle que des bords dans $ m $ avoir la direction de $ x $ to $ y $ tandis que les bords ne sont pas dans $ m $ avoir la direction de $ y $ to $ x $ , Ensuite, les nœuds dans $ x $ qui ne sont pas accessibles à partir de n'importe quel nœud dans $ z $ constituent le maximum ensemble saturé. Vous pouvez exécuter un simple bfs pour voir quels nœuds dans $ x $ est accessible à partir de nœuds dans $ z $ . La complexité de temps est $ o \ restante (\ sqrt {| v |} | e | \ droite) $

.

.