9
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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})$ $\endgroup$ – kodlu Sep 19 at 21:38
  • $\begingroup$ 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. $\endgroup$ – GMB Sep 19 at 21:46
  • $\begingroup$ I'm using the terminology here (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. $\endgroup$ – GMB Sep 19 at 21:48
6
$\begingroup$

No, you can't beat $\Theta(\sqrt{n})$ queries. I will explain how to formalize exfret's proof sketch 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.

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

$\endgroup$
  • $\begingroup$ "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.) $\endgroup$ – usul Sep 22 at 2:29
  • $\begingroup$ @usul, oops, yes, thank you! Fixed. $\endgroup$ – D.W. Sep 22 at 15:42
5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ This proof sketch sounds to me like it only works for nonadaptive algorithms (i.e. queries fixed in advance). $\endgroup$ – usul Sep 21 at 9:25
  • $\begingroup$ @usul Why would that be the case? Whp we are only using one branch of the decision tree anyways. $\endgroup$ – exfret Sep 21 at 11:02
  • $\begingroup$ 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. $\endgroup$ – exfret Sep 21 at 16:42
  • $\begingroup$ Thanks! I (somewhat arbitrarily) accepted the other fleshed-out version but it seems like you got it. Appreciate the response. $\endgroup$ – GMB Sep 22 at 0:06
  • 1
    $\begingroup$ @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. $\endgroup$ – exfret Sep 22 at 0:19

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.