P_Nyagolov's blog

Systems of Distinct Representatives
By P_Nyagolov, history, 9 years ago, In English

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! :)

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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! :)

    → Reply
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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... :(

        → Reply