tag:blogger.com,1999:blog-6555947.post4263070419264601822..comments2014-01-12T10:46:48.153-07:00Comments on The Geomblog: Probability of a graph being connected...Suresh Venkatasubramaniannoreply@blogger.comBlogger8125tag:blogger.com,1999:blog-6555947.post-53274625274347513902010-06-14T05:33:56.665-06:002010-06-14T05:33:56.665-06:00This topic is a little old, but I hope some of you...This topic is a little old, but I hope some of you will still read my question. I also need to find the probability of a graph to be connected except that this graph is not random but defined as follows:<br /><br />Let (x1, x2, ..., xn) be a sequence of points in R^n. Define graph G with edge (i,j) iff ||xi-xj|| <= R with R a given constant.<br /><br />I assume one possible way would be to compute the probability of existence of an edge and then use the results from connectivity on random graphs. I'm hoping there may be a more ad hoc way to proceed.Samhttp://www.blogger.com/profile/16243290481227012307noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-66277766309006100052009-06-13T08:50:41.621-06:002009-06-13T08:50:41.621-06:00I don't think it is that easy, Igor. Your recu...I don't think it is that easy, Igor. Your recurrence should have about the Bell number of terms..Valentashttp://www.blogger.com/profile/06522212024252543118noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-23805458417017336342009-06-10T16:37:13.535-06:002009-06-10T16:37:13.535-06:00Is the probability that any particular two vertice...Is the probability that any particular two vertices are connected a constant?<br /><br />In that case, I solved this problem in the past.<br /><br />Define:<br /><br />- P_connected(N): probability that a graph with N vertices is connected (given that the probability of any two vertices being connected is a constant P_e).<br /><br />- P_disconnected(N) = 1-P_connected(N)<br /><br />Now, you can write a recurrence that expresses P_connected(N) using P_connected(N-1) and P_disconnected(N-1). It should be straightforward, but very easy to mess up the details.<br /><br />Now, you have a formula to compute P_connected(N+1) from P_connected(N). Start with the base case P_connected(1) = 1, and build up to the desired N.Igor Ostrovskyhttp://igoro.com/noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-77873347278303441682009-06-10T16:23:11.169-06:002009-06-10T16:23:11.169-06:00Thanks all for the incredibly fast and useful comm...Thanks all for the incredibly fast and useful comments. Chandra and John, your references were dead on: the Provan and Bell Paper (referenced in the Karger paper) shows that the problem is #P-complete, and is even hard to approximate. <br /><br />Mohit, thanks for the pointer to Noga Alon's paper. <br /><br />Panos, yes I was interested in the case of differing probabilities.Sureshhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-39676360309536168592009-06-10T10:13:33.461-06:002009-06-10T10:13:33.461-06:00A good problem- you would think something like the...A good problem- you would think something like the matrix-tree theorem would solve it. <br /><br />I apologize if I misread your details or intent (weather you were interested in specifics graphs or asymptotics) as my comment is only appropriate if we are talking about the exact same problem.<br /><br />If you re-phrase graph connectivity as network reliability problem this problem is known to be hard ( #P complete: Provan and Ball " The complexity of counting cuts and of computing the probability that a graph is connected" SIAM J. Comput. 12/4, (1983), 777-788). The survey I was looking at was "A Note on the Complexity of Network Reliability Problems" Hans L. Bodlaender and Thomas Wolle.John Mounthttp://www.win-vector.com/blog/noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-79924765899576331322009-06-10T10:04:26.359-06:002009-06-10T10:04:26.359-06:00Does this assume that each edge has a different pr...Does this assume that each edge has a different probability of existence? <br /><br />Would the work of Newman (on graphs with arbitrary degree distributions) help in this respect? <br /><br />http://link.aps.org/doi/10.1103/PhysRevE.64.026118Panos Ipeirotishttp://www.blogger.com/profile/15283752183704062501noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-7393705298395812402009-06-10T10:03:47.198-06:002009-06-10T10:03:47.198-06:00The following paper of Noga Alon considers this qu...The following paper of Noga Alon considers this question. <br /><br />http://www.cs.tau.ac.il/~nogaa/PDFS/connect.pdf<br /><br />In summary, the graph will be connected whp if min-cut under p is at least clog n for some constant c and the bound is tight upto constants. <br /><br />MohitAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-20522126938444693542009-06-10T09:53:45.784-06:002009-06-10T09:53:45.784-06:00Check Karger's paper.
http://people.csail.mit....Check Karger's paper.<br />http://people.csail.mit.edu/karger/Papers/reliability-sirev.psChandrahttp://www.blogger.com/profile/00057069075567569157noreply@blogger.com