3
$\begingroup$

Given a bipartite graph $G = (V, U, E)$ such that $|V| = |U| =2^n$, one wants to sample an edge from $G$, uniformly at random, with the following operations:
1. One can sample $u \in U$ w.p $\frac{1}{|U|}$ ,or $v \in V$ w.p $\frac{1}{|V|}$.
2. There exists a polynomial time oracle, which can, given $u \in U$ (or $v \in V$), returns the degree of $u$ (the degree may be exponential in $n$).
3. The size of $E$ is unknown.
4. One can not test, given $u$ and $v$, if there is an edge between $u$ and $v$.
5. There is an oracle which can, given $u$, return $v$ such that $v$ uniformly chosen from the set of all neighbors of $u$.

If one has only polynomial time (in $n$) - is it possible to choose an edge uniformly at random? Is it possible to choose from a distribution close to uniform?

Without these restrictions, it would have been possible to choose $u$ w.p $\frac{deg(u)}{\sum deg(u)}$, and then choose $v$ u.a.r from the neighbors of $u$.

$\endgroup$
  • $\begingroup$ There seems to be a problem here, you give no way of knowing whether an edge is in the graph. In that case time considerations or not knowing the size of $E$ aren't the real barrier (your proposed solution when knowing the size of $E$ relies on the possibility to know who are the neighbors of $u$). You cannot differentiate two non isomorphic bipartite graphs having the same degree sequence under these conditions, so you can't sample edges (if you have a sampling procedure, after enough queries, with high probability you will be able to see all the edges and thus differentiate the graphs). $\endgroup$ – Ariel Jul 14 '18 at 14:02
  • $\begingroup$ thanks! I noticed it, and added an assumption: you can sample, given a node, a neighbor of it, uniformly at random $\endgroup$ – Vladimir K Jul 14 '18 at 14:13
  • 1
    $\begingroup$ You might be interested in this paper, where the setting is stronger (you can ask for the $j$'th neighbor) and a lower bound of $\Omega\left(\frac{|V|}{\sqrt{|E|}}\right)$ is claimed, which means that if $|E|=o((4-\epsilon)^n)$ you won't be able to sample uniformly in polynomial time (the bounds claimed are independent of the graphs topology). $\endgroup$ – Ariel Jul 14 '18 at 14:49
  • $\begingroup$ thank you, it helped me very much! (if you want to publish it as an answer, I will accept it) $\endgroup$ – Vladimir K Jul 14 '18 at 15:11
  • $\begingroup$ A question: does the lower bound hold for bipartite graphs as well? what if knowing the topology can help? $\endgroup$ – Vladimir K Jul 14 '18 at 16:01
1
$\begingroup$

You can't. Consider the bipartite graph with a single edge $(u_0,v_0)$, with $u_0,v_0$ randomly chosen at time of creation of the graph. Then sampling from $U$ has only a $1/2^n$ chance to hit $u_0$ each time, and sampling from $V$ has only a $1/2^n$ chance to hit $v_0$ each time, so you need exponentially many samples before you can find that edge.

In particular, after making $q$ samples, there is at most a $q/2^n$ chance that you receive either $u_0$ or $v_0$. Without sampling either $u_0$ or $v_0$ you have no hope of outputting the edge $(u_0,v_0)$. So after polynomially many samples, there's only an exponentially small chance of outputting that edge. Yet a correct algorithm must always output that edge every time. So in general, there's no way to solve your problem, or even to output from a distribution close to the desired one.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.