# Choosing a random edge with restrictions

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$.

• 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). Jul 14 '18 at 14:02
• thanks! I noticed it, and added an assumption: you can sample, given a node, a neighbor of it, uniformly at random Jul 14 '18 at 14:13
• 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). Jul 14 '18 at 14:49
• thank you, it helped me very much! (if you want to publish it as an answer, I will accept it) Jul 14 '18 at 15:11
• A question: does the lower bound hold for bipartite graphs as well? what if knowing the topology can help? Jul 14 '18 at 16:01

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.