Ensemble indépendant maximum d'un graphe bipartite

J'essaie de trouver l'ensemble indépendant maximal d'un graphique biparite.

J'ai trouvé ce qui suit dans certaines notes "13 mai 1998 - Université de Washington - CSE 521 - Applications du flux réseau" :

Problème:

Etant donné un graphe bipartite , trouver un ensemble indépendant qui est aussi grande que possible, où et . Un ensemble est indépendant s'il n'y a pas d'arêtes de entre les éléments de l'ensemble.$G = (U,V,E)$$U' \cup V'$$U' \subseteq U$$V' \subseteq V$$E$

Solution:

Construisez un diagramme de flux sur les sommets . Pour chaque arête il y a une arête de capacité infinie de à . Pour chaque , il y a un bord de capacité unitaire de à , et pour chaque , il y a un bord de capacité unitaire de à .$U \cup V \cup \{s,t\}$$(u,v) \in E$$u$$v$$u \in U$$s$$u$$v \in V$$v$$t$

Trouver une réduction de capacité finie , avec et . Soit et . L'ensemble est indépendant car il n'y a pas d'arêtes de capacité infinie traversant la coupe. La taille de la coupe est. Ceci, afin de rendre le jeu indépendant aussi grand que possible, nous faisons la coupe aussi petite que possible.$(S,T)$$s \in S$$t \in T$$U' = U \cap S$$V' = V \cap T$$U' \cup V'$$|U - U'| + |V - V'| = |U| + |V| - |U' \cup V'|$

Prenons donc ceci comme le graphique:

A - B - C
    |
D - E - F

Nous pouvons diviser cela en un graphe biparti comme suit $(U,V)=(\{A,C,E\},\{B,D,F\})$

Nous pouvons voir par la recherche de la force brute que le seul jeu indépendant maximum est . Essayons de travailler sur la solution ci-dessus:$A,C,D,F$

Ainsi, la matrice d'adjacence du réseau de flux construit serait:

$$\begin{matrix} & s & t & A & B & C & D & E & F \\ s & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ t & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ A & 1 & 0 & 0 & \infty & 0 & 0 & 0 & 0 \\ B & 0 & 1 & \infty & 0 & \infty & 0 & \infty & 0 \\ C & 1 & 0 & 0 & \infty & 0 & 0 & 0 & 0 \\ D & 0 & 1 & 0 & 0 & 0 & 0 & \infty & 0 \\ E & 1 & 0 & 0 & \infty & 0 & \infty & 0 & \infty \\ F & 0 & 1 & 0 & 0 & 0 & 0 & \infty & 0 \\ \end{matrix}$$

Voici où je suis coincé, la plus petite coupe de capacité finie que je vois est triviale: d'une capacité de 3.$(S,T) =(\{s\},\{t,A,B,C,D,E,F\})$

L'utilisation de cette coupe conduit à une solution incorrecte de:

$$U' = U \cap S = \{\}$$ $$V' = V \cap T = \{B,D,F\}$$ $$U' \cup V' = \{B,D,F\}$$

Alors que nous nous attendions à ? Quelqu'un peut-il repérer où je me suis trompé dans mon raisonnement / travail?$U' \cup V' = \{A,C,D,F\}$

Le complément d'un ensemble indépendant maximal est une couverture de sommets minimale.

Pour trouver une couverture de sommet minimale dans un graphe bipartite, voir le théorème de König .

La solution donnée est clairement incorrecte, comme vous le démontrez avec le contre-exemple. Notez que le graphique U + V est un composant connecté par les bords de capacité infinie. Par conséquent, chaque coupe valide devra contenir tous les A, B, C, D, E, F du même côté.

Essayer de retracer l'origine de la solution: http://www.cs.washington.edu/education/courses/cse521/01sp/flownotes.pdf cite Network Flows, par Ahuja, Magnanti et Orlin pour certains des problèmes. Ce livre est hors droits d'auteur et téléchargeable sur http://archive.org/details/networkflows00ahuj mais il ne semble pas contenir ce problème et cette solution (recherche de chaque occurrence de "bipartite").

Notez que le paragraphe d'explication de la solution ne montre pas que la plus petite coupe du graphique qu'il construit correspond à l' ensemble indépendant maximum . Il ne montre qu'un moyen d'obtenir un ensemble indépendant.

Et pourtant, vous pouvez voir ce que l'algorithme essaie de faire. Voici à quoi correspond le jeu indépendant maximal réel en termes de sa coupe s, t:

Le bord de capacité infinie qui rompt l'algorithme est souligné.

Je ne sais pas comment fixer l'algorithme à ce qui était prévu. Peut-être que le coût d'un bord infini devrait être nul s'il recule (c'est-à-dire où il va de S à T, mais passe de côté t à côté s)? Mais est-il toujours facile de trouver le min-cut / max-flow avec cette non-linéarité? De plus, en pensant à un moyen de faire le pont entre la solution de @Jukka Suomela et l'algorithme de la question, il y a une difficulté à passer de la correspondance maximale à la couverture minimale des sommets: tout en trouvant la correspondance maximale peut être effectuée par un max-flow comme un algorithme, comment en récupérez-vous la couverture minimale des sommets à l'aide d'un algorithme de type flux? Comme décrit ici, une fois la correspondance maximale trouvée, les arêtes entre U et V sont dirigées pour trouver la couverture de sommet minimale. Donc, encore une fois, cela ne montre pas qu'une simple application de min-cut / max-flow est tout ce qu'il faut pour résoudre ce problème.

$S$$T$$S$

La coupure devrait être sur le débit réel, pas sur les capacités. Puisque l'écoulement de s est fini, toute coupe {S, T} sera finie. Le reste est expliqué ci-dessus.

Je pense que vous n'avez pas besoin de connecter les bords dans les deux sens, même si le graphique d'origine n'était pas orienté. Parce que pour le réseau de flux, vous avez besoin d' un graphe orienté, vous pouvez considérer que les bords de à .$U$$V$

Ensuite, dans ce nouveau graphique , vous aurez un min-cut de 2, qui vous donnera la réponse .$G'$$\{A,C,D,F\}$