Hello everybody,
I have seen the name "Systems of Distinct Representatives" a few times in a short period of time so I decided to learn it. I have read about Hall's theorem and some of its applications but the thing is that I don't know some efficient way to find that system of distinct representatives. So the problem goes like this: We are given N sets S1,...,Sn of integers. We are to choose an integer from each set which we call a representative of that set. We want all sets to have different representatives. The best algorithm I know is to build a bipartite graph with sides the sets and the numbers and then the maximum matching will give us an answer. So that's why I learned the Hopcroft-Karp matching algorithm and assuming that the graph is built in O(E) time now I can solve the problem in O(E*sqrt(V)) which is worst case O(N^2*sqrt(N)).
However, I was told that it is possible to solve the problem in O(N^2). I will be really thankful if some of you can explain some more algorithms that can solve the problem faster and give me some problems if possible :)
Thanks in advance! :)
The problem is effectively equivalent to finding a maximum matching in an unweighted bipartite graph, as you have pointed out, but I don't think there is an O(n^2) algorithm for it: Matching in Graph Theory.
Okay, you really seem to be right since the maximum matching can be considered as the problem for finding SDR... Maybe it was due to miscalculation of the complexity since I wasn't the only one who got full score with O(N^4) with N<=500 (for the problem I told zxqfl). Thank you! :)
The number of edges is linear in the input size, so your algorithm is already O(N2). Actually I think your algorithm is O(N1.5).
How does this happen? If there are N sets and N^2 edges (which is the size of the input) then the matching is going to work in O(N^2*sqrt(N)). What do I miss?
Oh, I guess I misinterpreted what you meant. But are you sure the person who said you could solve in N^2 didn't mean "quadratic in the size of the input"? I don't think there is an O(E) bipartite matching algorithm.
During a training camp, were given the task to complete a latin rectangle MxN to a latin square NxN (N<=500, 1<=M<N). So assuming that the first M rows are filled, then we can find the M+1st row using SDR (System of Distinct Representatives). The author said that his solution does the same and finds the SDR in O(N^2) so the total complexity was O(N^3) but my O(N^4) implementation got full score with some optimizations. He tried to explain something which I didn't get and my friends that I asked said they didn't get it too. What the author said was that we will denote with B[i] the set represented by the number i. Initially we put all sets in a queue and take them one by one. If in the current set, there is a number that doesn't represent a set yet, then we make it a representative of the current set. Otherwise we take the first number (I am not sure how we needed to proceed if we again get to this set), push the set it represents into the queue and make it a representative of the current set. However, after I wanted to try this I didn't manage to understand how this works in O(N^2) and I thought that I misunderstood his explanation... :(