Sprouting Graphs

Computer Science Level 5

Given $n$ vertices $v_1,v_2,v_3, .. , v_n$ , we generate a graph $G$ as follows:

Go through each pair of vertices $v_i,v_j$
Flip a coin
If the coin is heads , create an edge $E_{ij}$ between $v_i,v_j$

Now, suppose we have two of these random graphs $G_1$ and $G_2$ . We want to determine if they are the same. Your task is to find the best case expected time of the most efficient algorithm we could come up with to do this.

The best case expected time $T$ can be said to satisfy $T = \Theta( n^a )$

for some integer $a$ . Find $a$ .

The answer is 0.

1 solution

Abhishek Sinha
Nov 2, 2015

We need to check the (un-ordered) pair of vertices $(v_1,v_2)$ to find out whether they are consistent or not (i.e., an edge is present in both $G_1$ and $G_2$ or in none of them). We continue the search as long as they are consistent so far. The first time we find an inconsistency, we terminate the search and declare the graphs to be different.

Since at every checking, with probability $\frac{1}{2}$ the search terminates, the expected running time of the algorithm is at most $1\times\frac{1}{2}+2\times \frac{1}{2^2} + 3\times \frac{1}{2^3}+\ldots =2$ , which is independent of $n$ . Thus the expected running time is simply $\Theta(1)$ (note that any constant within the $\Theta (\cdot)$ notation is absorbed). Hence $a=0$ .

More over, the best case is when you find at once that the first pair doesn't match, which takes only one check.

Laurent Shorts - 5 years, 1 month ago

Sprouting Graphs

The answer is 0.

1 solution

0 pending reports