Complexité de la recherche de classe, sélection des entrées dans la matrice

Question

Supposons que j'ai une matrice avec des entrées soit $x$ ou $y$, où nombre de lignes = nombre de colonnes = $n$.Si je veux sélectionner/encercler $n$ entrées telles que pour chaque ligne, une seule exactement est encerclée, pour chaque colonne, exactement une est encerclée également, et de telle sorte que toutes les entrées encerclées ne soient que $x$ (si un tel cercle d'entrées existe), à ​​quelle classe de complexité appartient-il ?Merci!

Answer 1

Laisser $U$ être l'ensemble des lignes de la matrice donnée et $V$ l'ensemble des colonnes.Pour chaque $x$ à la rangée $i$ et colonne $j$, ajoutez une arête entre les rangées $i$ et colonne $j$.Vous aurez un graphe biparti (non pondéré) $G=(U,V,E)$.Le problème est de trouver un correspondance parfaite, ce qui revient fondamentalement à trouver la correspondance maximale de $G$.

Il y a plusieurs algorithmes qui calculent la correspondance de cardinalité maximale.Par exemple, L'algorithme de Hopcroft-Karp court dans $O(\max(|E|\sqrt {|V|}, |V|^2)$.

On peut donc dire que la classe de complexité du problème posé est dans $O(n^{2.5})$ depuis $|E|\le n^2$ et $|V|= 2n$.