1
$\begingroup$

I am trying to find an algorithm to determine whether a $N\times N$ matrix of ones and zeroes could have a sublist of ones, such that in that sublist we have only one $1$ from each row or column.

$\endgroup$
3
$\begingroup$

This is the perfect matching problem in a bipartite graph: construct a bipartite graph with nodes $1,...,N$ on one side and nodes $-1,...,-N$ on the other side, and with an edge from $i$ to $-j$ if your matrix has a 1 in row $i$, column $j$. Then a perfect matching in this graph corresponds to a subset of ones in the matrix having the property that no two of them are in the same row or column.

Textbook algorithm

The Hopcroft-Karp algorithm solves the problem; it can determine if a perfect matching exists in time $O(\sqrt{N} M)$ where $M$ is the number of ones in your matrix (clearly, $M \le N^2$).

A simpler randomized algorithm

If you are satisfied with a randomized algorithm (with a small probability of error), there is indeed a conceptually simpler algorithm due to László Lovász. Create a new matrix $X$ in which every 1 in the original matrix is replaced by a random integer between 1 and some bound $P>100 \cdot N$; zeros in the original matrix remain zeros in $X$. Compute the determinant of $X$. If $det(X) \neq 0$, then for sure the original matrix has a perfect matching; if $det(X) = 0$, then with probability at least $1-1/100$, the original matrix does not have a perfect matching. (If you want to be sure that the value of the determinant does not overflow, you can do the computations modulo $P$ if you choose $P$ to be prime.) Computing the determinant will take time $O(N^3)$ with standard decomposition methods.

An even simpler (and slower) method

The simplest polynomial-time algorithm I know for bipartite perfect matching is due to Linial, Samorodnitsky and Wigderson and runs in time $O(N^4 \log N)$. Let $c_j$ denote the sum of the elements in column $j$. The algorithm is as follows:

For $N^2 \log N$ iterations do:
1. Normalize each column so that it sums to 1
2. Normalize each row so that it sums to 1
3. Compute $c_1,\ldots,c_N$
4. If $\sum_{j=1}^N (c_j-1)^2 < 1/N$ return YES
Return NO

If $N$ is tiny

If you want something even simpler (?) to implement (but much, much slower if $N$ is large), you could just enumerate all permutations over $N$ elements, and for each of these check if the corresponding set satisfies your property. That is, for each permutation $\pi: \{1,\ldots,N\} \to \{1,\ldots,N\}$, you check if cell $(i, \pi(i))$ of the matrix contains a 1, for each $i=1,\ldots,N$. The standard libraries of some programming languages have support for generating all permutations of a set; for example, itertools.permutations in Python or next_permutation in C++. However, this approach based on enumeration will take time about $N \cdot N!$, which is more than exponential in $N$. It will probably only be acceptable if $N$ is at most around 10-12.

$\endgroup$
  • $\begingroup$ Is there anything simpler? I am not trying to find a the set. Just to know if exists or not. $\endgroup$ – bilanush Jan 22 at 17:00
  • $\begingroup$ I updated my answer with two simpler methods. Anyway, I would not say Hopcroft-Karp is hard to implement. $\endgroup$ – Vincenzo Jan 22 at 18:05

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.