<p>Let’s assume we can only query the <span class="math-container">$i$</span>th edge of a given vertex’s adjacency list (which I am assuming is not sorted) or whether two given vertices are adjacent. In this case it should take <span class="math-container">$\sqrt n$</span> queries to even find a cycle. This is because there is a <span class="math-container">$1-o(1)$</span> chance that all our queries of the first type return different vertices and that all of our queries of the second type return that the two vertices are not connected.</p>

<p>Please correct me if I am wrong somewhere or misunderstanding the problem.</p>

CC BY-SA 4.0
2019-09-21T09:25:22.517Z
This proof sketch sounds to me like it only works for nonadaptive algorithms (i.e. queries fixed in advance).
usul
CC BY-SA 4.0
2019-09-21T11:02:49.487Z
@usul Why would that be the case? Whp we are only using one branch of the decision tree anyways.
exfret
CC BY-SA 4.0
2019-09-21T16:42:59.470Z
Perhaps I should clarify. It should be clear that if we receive answers to our queries as prescribed then we cannot output a 4-cycle with constant probability. However, for any decision tree of depth $o(\sqrt n)$ there is a $1-o(1)$ chance we are sent down such a branch.
exfret
CC BY-SA 4.0
2019-09-22T00:06:01.323Z
Thanks!  I (somewhat arbitrarily) accepted the other fleshed-out version but it seems like you got it.  Appreciate the response.
GMB
CC BY-SA 4.0
2019-09-22T00:19:18.403Z
@GMB I think you made the correct decision; the other one is a much higher quality answer and deserves to be seen first by others.
exfret
CC BY-SA 4.0
2019-09-21T01:35:25.980Z
2019-09-21T01:35:25.980Z
exfret
<p>No, you can't beat <span class="math-container">$\Theta(\sqrt{n})$</span> queries.  I will explain how to formalize <a href="https://cstheory.stackexchange.com/a/45569/5038">exfret's proof sketch</a> of this, in a way that works for adaptive algorithms.  This is all anticipated in exfret's answer; I am just filling in some of the details.</p>

<p>Consider any (possibly adaptive) algorithm that issues a sequence of queries, where each query is either "fetch the <span class="math-container">$i$</span>th edge of vertex <span class="math-container">$v$</span>'s adjacency list" or "test whether vertices <span class="math-container">$v,w$</span> are connected by an edge".  We can assume that no query is repeated, as any algorithm that repeats a query can be transformed to one that never repeats any query.  Similarly, we can assume that the algorithm never does a connectivity query on any pair of vertices that are already known to be connected by an edge (namely, testing <span class="math-container">$v,w$</span> when <span class="math-container">$w$</span> was previously returned by a fetch query on <span class="math-container">$v$</span>, or <span class="math-container">$v$</span> was previously returned by a fetch query on <span class="math-container">$w$</span>, or we previously tested connectivity of <span class="math-container">$w,v$</span>).</p>

<p>Let <span class="math-container">$E_k$</span> denote the event that, during the first <span class="math-container">$k$</span> queries, no vertex <span class="math-container">$w$</span> is returned by more than one fetch-query, and no fetch-query returns a vertex that was previously queried, and that no connectivity-test-query returns "connected".  We'll prove that <span class="math-container">$\Pr[E_q] = 1-o(1)$</span> if <span class="math-container">$q=o(\sqrt{n})$</span>.  It follows that no algorithm that makes <span class="math-container">$o(\sqrt{n})$</span> queries can have a constant probability of finding a 4-cycle.</p>

<p>How do we prove this?  Let's compute <span class="math-container">$\Pr[E_k|E_{k-1}]$</span>.  There are two cases: either the <span class="math-container">$k$</span>th query is a fetch query, or it is an connectivity-test query:</p>

<ol>
<li><p>If the <span class="math-container">$k$</span>th query is a fetch query on vertex <span class="math-container">$v$</span>, there are <span class="math-container">$2(k-1)$</span> vertices mentioned among the first <span class="math-container">$k-1$</span> queries, and if the <span class="math-container">$k$</span>th query returns one of those then we will have <span class="math-container">$\neg E_k$</span>, otherwise we will have <span class="math-container">$E_k$</span>.  Now the response to the <span class="math-container">$k$</span>th query is uniformly distributed on a set <span class="math-container">$S$</span> of vertices, where <span class="math-container">$S$</span> contains all vertices that haven't been returned by prior fetch queries on <span class="math-container">$v$</span>, so the response to the <span class="math-container">$k$</span>th query is uniformly distributed on a set of size at least <span class="math-container">$n-k+1$</span>.  The probability of hitting at least one of these is <span class="math-container">$\le 2(k-1)/(n-k+1)$</span>, so in this case, <span class="math-container">$\Pr[E_k|E_{k-1}] \ge 1 - 2(k-1)/(n-k+1)$</span>.</p></li>
<li><p>If the <span class="math-container">$k$</span>th query is a connectivity-test query, then <span class="math-container">$\Pr[E_k|E_{k-1}] \ge 1 - 1/\sqrt{n}$</span>.</p></li>
</ol>

<p>In either case, if <span class="math-container">$q=o(\sqrt{n})$</span> we have</p>

<p><span class="math-container">$$\Pr[E_k|E_{k-1}] \ge 1 - {2(k-1) \over (n-k+1)}.$$</span></p>

<p>Now,</p>

<p><span class="math-container">$$\Pr[E_q] = \prod_{k=1}^q \Pr[E_k|E_{q-1}].$$</span></p>

<p>If <span class="math-container">$k \le q \le \sqrt{n}$</span>, then</p>

<p><span class="math-container">$$\Pr[E_k|E_{k-1}] \ge 1 - {2q \over n - q},$$</span></p>

<p>so</p>

<p><span class="math-container">$$\Pr[E_q] \ge (1 - {2 q  \over n - q})^q.$$</span></p>

<p>The right-hand side is approximately <span class="math-container">$\exp \{ - 2q^2/(n-q)\}$</span>.  When <span class="math-container">$q = o(\sqrt{n})$</span>, this is <span class="math-container">$1 -o(1)$</span>.</p>

<p>In conclusion: <span class="math-container">$\Pr[E_q] = 1-o(1)$</span> when <span class="math-container">$q=o(\sqrt{n})$</span>.  It follows that you need <span class="math-container">$\Omega(\sqrt{n})$</span> to have constant probability of finding any cycle (let alone a 4-cycle).</p>

CC BY-SA 4.0
2019-09-22T02:29:55.797Z
"If the kth query is a connectivity-test query, then $Pr[Ek|Ek−1]≥1−1/n$." I'm thinking $1-1/\sqrt{n}$? (Even if so, the conclusion still goes through of course.)
usul
CC BY-SA 4.0
2019-09-22T15:42:52.563Z
@usul, oops, yes, thank you!  Fixed.
D.W.
CC BY-SA 4.0
2019-09-21T23:43:53.050Z
2019-09-22T21:34:48.383Z
2019-09-22T21:34:48.383Z
D.W.
<p>Let <span class="math-container">$G \sim G(n, n^{-1/2})$</span> be a random graph on <span class="math-container">$\approx n^{3/2}$</span> edges.  With very high probability, <span class="math-container">$G$</span> has many <span class="math-container">$4$</span>-cycles.  Our goal is to output any one of these <span class="math-container">$4$</span>-cycles as quickly as possible.</p>

<p>Supposing we have access to <span class="math-container">$G$</span> in adjacency list form, we can succeed with constant probability in <span class="math-container">$O(\sqrt{n})$</span> time as follows: pick any node <span class="math-container">$v$</span> and start generating random <span class="math-container">$2$</span>-paths starting from <span class="math-container">$v$</span>; once we find two distinct <span class="math-container">$2$</span>-paths that share an endpoint, we are done.  There are <span class="math-container">$n$</span> possible endpoints, and by the birthday paradox we will succeed with constant probability after discovering about <span class="math-container">$\sqrt{n}$</span> of them.</p>

<p>Can we do better?  In particular, is a constant-time algorithm that succeeds with constant probability possible?</p>

CC BY-SA 4.0
2019-09-19T21:38:26.380Z
It seems to me this graph has too few edges to have the property you want, if you are using the standard terminology, it is like a $G(n,p)$ sample with $p=(\sqrt{n}/C(n,2))=O(n^{-3/2})$
kodlu
CC BY-SA 4.0
2019-09-19T21:46:10.960Z
Thanks, you're right that I meant $p = n^{-1/2}$ (edited).  These graphs will have $C_4$s any time two nodes share $\ge 2$ neighbors, which happens with constant probability per node pair.
GMB
CC BY-SA 4.0
2019-09-19T21:48:21.303Z
I'm using the terminology here (https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model), where each edge is included independently with probability $p$ -- so, $p \cdot {n \choose 2}$ edges in expectation.
GMB
<graph-theory><graph-algorithms><property-testing><random-graphs>
How long does it take to find a short cycle in a random graph?
GMB
# How long does it take to find a short cycle in a random graph?

(Asked by: username_0 on 2019-09-19)

Let $G \sim G(n, n^{-1/2})$ be a random graph on $\approx n^{3/2}$ edges. With very high probability, $G$ has many $4$-cycles. Our goal is to output any one of these $4$-cycles as quickly as possible.

Supposing we have access to $G$ in adjacency list form, we can succeed with constant probability in $O(\sqrt{n})$ time as follows: pick any node $v$ and start generating random $2$-paths starting from $v$; once we find two distinct $2$-paths that share an endpoint, we are done. There are $n$ possible endpoints, and by the birthday paradox we will succeed with constant probability after discovering about $\sqrt{n}$ of them.

Can we do better? In particular, is a constant-time algorithm that succeeds with constant probability possible?

**Tags:** graph-theory, graph-algorithms, property-testing, random-graphs

> **Comments:**
> **username_1**: It seems to me this graph has too few edges to have the property you want, if you are using the standard terminology, it is like a $G(n,p)$ sample with $p=(\sqrt{n}/C(n,2))=O(n^{-3/2})$  
> **username_0**: Thanks, you're right that I meant $p = n^{-1/2}$ (edited).  These graphs will have $C_4$s any time two nodes share $\ge 2$ neighbors, which happens with constant probability per node pair.  
> **username_0**: I'm using the terminology here (https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model), where each edge is included independently with probability $p$ -- so, $p \cdot {n \choose 2}$ edges in expectation.  

---

## 2 answers

### Answer by username_4 on 2019-09-21. Score: 6 | Accepted answer

No, you can't beat $\Theta(\sqrt{n})$ queries. I will explain how to formalize [username_2's proof sketch](https://cstheory.stackexchange.com/a/45569/5038) of this, in a way that works for adaptive algorithms. This is all anticipated in username_2's answer; I am just filling in some of the details.

Consider any (possibly adaptive) algorithm that issues a sequence of queries, where each query is either "fetch the $i$th edge of vertex $v$'s adjacency list" or "test whether vertices $v,w$ are connected by an edge". We can assume that no query is repeated, as any algorithm that repeats a query can be transformed to one that never repeats any query. Similarly, we can assume that the algorithm never does a connectivity query on any pair of vertices that are already known to be connected by an edge (namely, testing $v,w$ when $w$ was previously returned by a fetch query on $v$, or $v$ was previously returned by a fetch query on $w$, or we previously tested connectivity of $w,v$).

Let $E\_k$ denote the event that, during the first $k$ queries, no vertex $w$ is returned by more than one fetch-query, and no fetch-query returns a vertex that was previously queried, and that no connectivity-test-query returns "connected". We'll prove that $\Pr[E\_q] = 1-o(1)$ if $q=o(\sqrt{n})$. It follows that no algorithm that makes $o(\sqrt{n})$ queries can have a constant probability of finding a 4-cycle.

How do we prove this? Let's compute $\Pr[E\_k|E\_{k-1}]$. There are two cases: either the $k$th query is a fetch query, or it is an connectivity-test query:

1. If the $k$th query is a fetch query on vertex $v$, there are $2(k-1)$ vertices mentioned among the first $k-1$ queries, and if the $k$th query returns one of those then we will have $\neg E\_k$, otherwise we will have $E\_k$. Now the response to the $k$th query is uniformly distributed on a set $S$ of vertices, where $S$ contains all vertices that haven't been returned by prior fetch queries on $v$, so the response to the $k$th query is uniformly distributed on a set of size at least $n-k+1$. The probability of hitting at least one of these is $\le 2(k-1)/(n-k+1)$, so in this case, $\Pr[E\_k|E\_{k-1}] \ge 1 - 2(k-1)/(n-k+1)$.
2. If the $k$th query is a connectivity-test query, then $\Pr[E\_k|E\_{k-1}] \ge 1 - 1/\sqrt{n}$.

In either case, if $q=o(\sqrt{n})$ we have

$$\Pr[E\_k|E\_{k-1}] \ge 1 - {2(k-1) \over (n-k+1)}.$$

Now,

$$\Pr[E\_q] = \prod\_{k=1}^q \Pr[E\_k|E\_{q-1}].$$

If $k \le q \le \sqrt{n}$, then

$$\Pr[E\_k|E\_{k-1}] \ge 1 - {2q \over n - q},$$

so

$$\Pr[E\_q] \ge (1 - {2 q \over n - q})^q.$$

The right-hand side is approximately $\exp \{ - 2q^2/(n-q)\}$. When $q = o(\sqrt{n})$, this is $1 -o(1)$.

In conclusion: $\Pr[E\_q] = 1-o(1)$ when $q=o(\sqrt{n})$. It follows that you need $\Omega(\sqrt{n})$ to have constant probability of finding any cycle (let alone a 4-cycle).

> **Comments:**
> **username_3**: "If the kth query is a connectivity-test query, then $Pr[Ek|Ek−1]≥1−1/n$." I'm thinking $1-1/\sqrt{n}$? (Even if so, the conclusion still goes through of course.)  
> **username_4**: @username_3, oops, yes, thank you!  Fixed.  

---

### Answer by username_2 on 2019-09-21. Score: 5

Let’s assume we can only query the $i$th edge of a given vertex’s adjacency list (which I am assuming is not sorted) or whether two given vertices are adjacent. In this case it should take $\sqrt n$ queries to even find a cycle. This is because there is a $1-o(1)$ chance that all our queries of the first type return different vertices and that all of our queries of the second type return that the two vertices are not connected.

Please correct me if I am wrong somewhere or misunderstanding the problem.

> **Comments:**
> **username_3**: This proof sketch sounds to me like it only works for nonadaptive algorithms (i.e. queries fixed in advance).  
> **username_2**: @username_3 Why would that be the case? Whp we are only using one branch of the decision tree anyways.  
> **username_2**: Perhaps I should clarify. It should be clear that if we receive answers to our queries as prescribed then we cannot output a 4-cycle with constant probability. However, for any decision tree of depth $o(\sqrt n)$ there is a $1-o(1)$ chance we are sent down such a branch.  
> **username_0**: Thanks!  I (somewhat arbitrarily) accepted the other fleshed-out version but it seems like you got it.  Appreciate the response.  
> **username_2**: @username_0 I think you made the correct decision; the other one is a much higher quality answer and deserves to be seen first by others.  

---

