Correspondance un à plusieurs maximum

Question

Laisser $G = (X+Y,E)$ être un graphe biparti et $k\geq 1$un nombre entier. Un maximum$k$-matching est un sous-ensemble de$E$ dans lequel chaque sommet de $X$ est adjacent à au plus $k$ arêtes et chaque sommet de $Y$ est adjacent à au plus $1$ bord.

Une cardinalité maximale $k$-matching peut être trouvé par l'algorithme suivant:

• Créer $k$ copies de chaque sommet $x\in X$, de sorte que chaque copie est adjacente à tous les voisins de $x$ dans $Y$.
• Trouvez une correspondance maximale dans le graphique résultant.

Sa complexité d'exécution pour un graphe avec $n$ sommets et $m$ arêtes, en utilisant l'algorithme de Hopcroft-Karp, est $O(k m\sqrt{k n}) =O(k^{3/2}\cdot m\sqrt{n})$.

Je suis intéressé par l'algorithme alternatif suivant:

• Répéter $k$ fois:

  • Trouvez une correspondance maximale dans $G$.
  • Supprimez les sommets correspondants de $Y$ du graphique.

Sa complexité d'exécution est $O(k \cdot m\sqrt{n})$.

Mais cet algorithme trouve-t-il toujours un maximum $k$-correspondant à?

Answer 1

Non. Voici un contre-exemple: $X=\{a,b\}, Y=\{c,d,e,f\}, E=\{ac, ad, ae, be, bf\}, k=2$. La première itération de votre algorithme pourrait choisir$\{ae,bf\}$ (en particulier, le bord $ae$), empêchant de trouver une solution même s'il en existe une: $\{ac, ad, be, bf\}$.