comtalyst's blog

[Solved] Is there any faster way to solve Graph Realization problem?
By comtalyst, 7 years ago, In English

Problem statement : Given a degree sequence D. Can we create a simple graph (graph without self loops and parallel edges) from D?

This is a classical problem that can be solved by using Havel-Hakimi algorithm or Erdős–Gallai theorem. Both of them have time complexity O(n^2). But I have found a task with N <= 100000 which is incompatible with O(n^2) algorithms. Is there any faster method to solve this?

(Edited) There are no any special conditions in this task

(Edited) Solved!! Optimize Erdős-Gallai Algorithm by using binary search to find min(di,k) of each k efficiently. New time complexity is O(n log n). Thanks 300iq and animeshf for this idea!

Link for Erdős-Gallai algorithm : https://en.wikipedia.org/wiki/Erdős–Gallai_theorem

Thanks everyone for replying.

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

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Gale-Ryser may work if your graph is bipartite.

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

    Thanks for reply. But for now, I cant find any special conditions in this task.

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

Havel Hakimi can be implemented in such a way so that the complexity becomes O(Summation of degrees of all nodes * log(n)) which can be smaller than O(n^2) depending on the input constraint. What is the constraint on the degrees of the nodes in your problem?

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

    Sadly, It seems there is no special condition about this too.... ;( All degrees can be at most N.

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

      I guess you have to output the edges, so sum(degrees) can't be too large, because you have to print out 2*sum(degrees)/2 numbers, which would be impossible for numbers like > 10^7.

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

        Maybe YES/NO task.

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

          Yes,and there are 10 queries per test case. Time limit is just 1 sec.

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

            So you can check Erdos-Gallai theotem with binary search and partial sums

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

              That looks cool! I completely forgot about binary search. I will try this soon.

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

Auto comment: topic has been updated by comtalyst (previous revision, new revision, compare).

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

Seems like some people wrote a paper on optimizing Erdős-Gallai from O(n2) to O(nlogn) (or O(n) if D is already sorted). The relevant part is the 15 line pseudocode on page 6 (It is pretty self-explanatory).

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

Auto comment: topic has been updated by comtalyst (previous revision, new revision, compare).

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Can you share the problem link?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it

      This problem come from a thai competitive programming site named CodeCube. Here is the problem link.

      Unfortunately, official problem description and the whole site is in Thai only (but it isnt hard to be analyzed). And you will have to register before submit.

      Here is my brief English translation: Given Q — number of queries (Q <= 10). Each query contains N — number of vertices in the graph (N <= 100000) followed by a degree sequence, each of them doesnt exceed N. For each query, answer "Yes" or "No".

      → Reply