Complexity of class finding selection of entries in matrix

Question

Suppose I have a matrix with entries either $x$ or $y$, where the number of rows = number of columns = $n$. If I want to select/circle $n$ entries such that for each row, only exactly one is circled, for each column, also exactly one is circled, and such that all entries circled are only $x$ (if such a circling of entries exists), what complexity class does this belong to? Thanks!

Answer 1

Let $U$ be the set of rows in the given matrix and $V$ the set of columns. For each $x$ at row $i$ and column $j$, add an edge between row $i$ and column $j$. You will have an (unweighted) bipartite graph $G=(U,V, E)$. The problem is to find a perfect matching, which is basically the same as find the maximum matching of $G$.

There are various algorithms that compute the maximum cardinality matching. For example, The Hopcroft–Karp algorithm runs in $O(\max(|E|\sqrt {|V|}, |V|^2)$.

So, we can say that the complexity class of the problem in the question is in $O(n^{2.5})$ since $|E|\le n^2$ and $|V|= 2n$.