Abbinamento massimo uno-a-molti
Permettere $G = (X+Y,E)$ essere un grafo bipartito e $k\geq 1$un numero intero. Un massimo$k$-matching è un sottoinsieme di$E$ in cui ogni vertice di $X$ è adiacente al massimo $k$ bordi e ogni vertice di $Y$ è adiacente al massimo $1$ bordo.
Una cardinalità massima $k$-matching può essere trovato dal seguente algoritmo:
- Creare $k$ copie di ogni vertice $x\in X$, in modo che ogni copia sia adiacente a tutti i vicini di $x$ in $Y$.
- Trova una corrispondenza massima nel grafico risultante.
La sua complessità di runtime per un grafico con $n$ vertici e $m$ bordi, utilizzando l'algoritmo di Hopcroft-Karp, è $O(k m\sqrt{k n}) =O(k^{3/2}\cdot m\sqrt{n})$.
Sono interessato al seguente algoritmo alternativo:
Ripetere $k$ volte:
- Trova una corrispondenza massima in $G$.
- Rimuovi i vertici corrispondenti di $Y$ dal grafico.
La sua complessità in fase di esecuzione è $O(k \cdot m\sqrt{n})$.
Ma questo algoritmo trova sempre un massimo $k$-matching?
Risposte
No. Ecco un controesempio: $X=\{a,b\}, Y=\{c,d,e,f\}, E=\{ac, ad, ae, be, bf\}, k=2$. La prima iterazione del tuo algoritmo potrebbe scegliere$\{ae,bf\}$ (in particolare, il bordo $ae$), impedendo di trovare una soluzione anche se ne esiste una: $\{ac, ad, be, bf\}$.