Working on network design this summer I have come across certain applications that have inspired me to ask the following question:

Given an undirected connected graph $G=(V,E)$ what is the minimum number of vertices, $k$, sampled uniformly and independently at random from $V$ (without replacement), such that the induced subgraph on those vertices is connected w.h.p.?

Notice, I am not looking for a way to sample a connected (induced) subgraph, I am looking for a probabilistic guarantee that I have sampled enough vertices to end up with a connected induced subgraph.

Does this sounds familiar to anyone? A quick search was not very promising so I decided to ask here if anyone has any references or even directions to point me at.

I am assuming the answer would be a function of some structural property(/ies) of the graph, like connectedness, minimum degree, expansion, etc..

  • $\begingroup$ I guess high minimum degree isn't enough: Start with a few separate, large cliques; then connect all these vertices to a single central vertex. Now we must sample that central vertex in order to ensure connectivity w.h.p. $\endgroup$ – usul Jul 14 '15 at 19:22
  • $\begingroup$ Yep, exactly. It can't be just that. Whenever the min cut is small you'd have problems like that. $\endgroup$ – Konstantinos Koiliaris Jul 14 '15 at 19:55

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.