1
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.