I want an algorithm that takes the following

Input: $M,N,k,d$ positive integers such that $kM = dN$.

and produces the following

Output: Random bipartite graph, with $M$ vertices all of degree $k$ on one partition, and $N$ vertices all of degree $d$ on the other partition. No loops allowed. The output should be uniformly distributed among all possible graphs.

Does an algorithm like this exist? If so please provide a reference.

  • 1
    $\begingroup$ What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. $\endgroup$ – Raphael Jun 1 '16 at 15:17
  • $\begingroup$ @Raphael This is not homework (if it is, can you point out a course or textbook?). I need to generate this ensemble of random bipartite graphs to test the statistical properties of a different algorithm. I tried placing links at random, checking that no self-loops or parallel edges were created and checking the degrees, but this leads to contradictions and the generator gets stuck frequently. $\endgroup$ – becko Jun 1 '16 at 15:28
  • 1
    $\begingroup$ Googling for random graph generation leads to many, many resources. Which have you tried, and why have you dismissed them? $\endgroup$ – Raphael Jun 1 '16 at 18:25
  • $\begingroup$ @Raphael Did you find anything for random bipartite bi-regular graphs?? $\endgroup$ – becko Jun 1 '16 at 18:45
  • $\begingroup$ I don't know. I suspect what Raphael is implying is: We want you to search before asking here, and tell us in the question what research you've done. What have you looked at? Have you done a literature search to look through the literature on generating random graphs, to see if any of it covers bipartite regular graphs? Have you looked at known techniques for generating regular graphs, to see if any of them can be adapted to this situation? Have you search Google Scholar to look for algorithms for generating a random biregular graph? $\endgroup$ – D.W. Jun 2 '16 at 6:53

Your Answer

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

Browse other questions tagged or ask your own question.