Сколько времени нужно, чтобы найти короткий цикл в случайном графе?

Позволять $G \sim G(n, n^{-1/2})$ быть случайным графом на $\approx n^{3/2}$ кромки. С очень высокой вероятностью, $G$ имеет много $4$ -циклов. Наша цель - вывести любой из этих $4$ -циклы как можно быстрее.

Предположим, у нас есть доступ к $G$ в форме списка смежности, мы можем добиться успеха с постоянной вероятностью в $O(\sqrt{n})$ время следующим образом: выбрать любой узел $v$ и начать генерировать случайные $2$ пути, начинающиеся с $v$ ; как только мы находим два разных $2$ - пути, которые разделяют конечную точку, мы закончили. Есть $n$ возможные конечные точки, и по парадоксу дня рождения мы добьемся успеха с постоянной вероятностью, узнав о $\sqrt{n}$ из них.

Можем ли мы сделать лучше? В частности, возможен ли алгоритм с постоянным временем, который успешно работает с постоянной вероятностью?

graph-theory graph-algorithms property-testing random-graphs GMB
источник

Мне кажется, что у этого графа слишком мало ребер, чтобы иметь желаемое свойство, если вы используете стандартную терминологию, это похоже на

G (n, p)

$G(n,p)$ образец с

p = (\sqrt{n} / C (n, 2)) = O (n^{- 3 / 2})

$p=(\sqrt{n}/C(n,2))=O(n^{-3/2})$

Кодлу

Спасибо вы правы что я имел ввиду

p = n^{- 1 / 2}

$p = n^{-1/2}$ (Под редакцией). Эти графики будут иметь

C_{4}

$C_4$ в любое время два узла разделяют

\geq 2

$\ge 2$ соседи, что происходит с постоянной вероятностью для каждой пары узлов.

GMB

Я использую здесь терминологию ( en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model ), где каждое ребро включается независимо с вероятностью

p

$p$ Итак, ребер в ожидании.

p \cdot (\binom{n}{2})

$p \cdot {n \choose 2}$

GMB

Ответы:

Нет, вы не можете превзойти запросы . Я объясню, как формализовать набросок доказательства exfret этого, таким образом, который работает для адаптивных алгоритмов. Это все ожидается в ответе exfret; Я просто заполняю некоторые детали. $\Theta(\sqrt{n})$

Рассмотрим любой (возможно, адаптивный) алгоритм, который выдает последовательность запросов, где каждый запрос либо «выбирает й край списка смежности вершины », либо «проверяет связаны ли вершины ребром». Можно предположить, что ни один запрос не повторяется, так как любой алгоритм, который повторяет запрос, может быть преобразован в алгоритм, который никогда не повторяет какой-либо запрос. Точно так же мы можем предположить, что алгоритм никогда не выполняет запрос на соединение по любой паре вершин, которые, как известно, уже связаны ребром (а именно, проверяют когда был ранее возвращен запросом выборки на , или был ранее возвращенный запросом на $i$ $v$ $v,w$ $v,w$ $w$ $v$ $v$ $w$ , или мы ранее проверили связность ). $w,v$

Пусть обозначает событие, когда во время первых запросов ни одна вершина не возвращается более чем одним запросом на выборку, и ни один запрос на выборку не возвращает вершину, которая была запрошена ранее, и что ни один запрос на соединение не возвращает "подключенный ». Мы докажем, что если . Отсюда следует, что ни один алгоритм, который делает запросов, не может иметь постоянную вероятность нахождения 4-цикла. $E_k$ $k$ $w$ $\Pr[E_q] = 1-o(1)$ $q=o(\sqrt{n})$ $o(\sqrt{n})$

Как мы докажем это? Давайте вычислим . Существует два случая: либо й запрос является запросом выборки, либо запросом на проверку соединения: $\Pr[E_k|E_{k-1}]$ $k$

Если й запрос является запросом выборки для вершины , среди первых запросов упоминается вершины , и если й запрос возвращает один из них, то у нас будет , в противном случае у нас будет . Теперь ответ на й запрос равномерно распределен по набору вершин, где содержит все вершины, которые не были возвращены предыдущими запросами выборки на , поэтому ответ на й запрос равномерно распределен по набору размером не менее $k$ $v$ $2(k-1)$ $k-1$ $k$ $\neg E_k$ $E_k$ $k$ $S$ $S$ $v$ $k$ $n-k+1$ , Вероятность поражения хотя бы одного из них равна , поэтому в этом случае . $\le 2(k-1)/(n-k+1)$ $\Pr[E_k|E_{k-1}] \ge 1 - 2(k-1)/(n-k+1)$
Если й запрос является запросом для проверки соединения, то . $k$ $\Pr[E_k|E_{k-1}] \ge 1 - 1/\sqrt{n}$

В любом случае, если мы имеем $q=o(\sqrt{n})$

Pr [E_{k} | E_{k - 1}] \geq 1 - \frac{2 (k - 1)}{(n - k + 1)} .

$\Pr[E_k|E_{k-1}] \ge 1 - {2(k-1) \over (n-k+1)}.$

Сейчас же,

Pr [E_{q}] = \prod_{k = 1}^{q} Pr [E_{k} | E_{q - 1}] .

$\Pr[E_q] = \prod_{k=1}^q \Pr[E_k|E_{q-1}].$

Если , то $k \le q \le \sqrt{n}$

Pr [E_{k} | E_{k - 1}] \geq 1 - \frac{2 q}{n - q},

$\Pr[E_k|E_{k-1}] \ge 1 - {2q \over n - q},$

так

Pr [E_{q}] \geq (1 - \frac{2 q}{n - q})^{q} .

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

Правая часть примерно равна . Когда , это . $\exp \{ - 2q^2/(n-q)\}$ $q = o(\sqrt{n})$ $1 -o(1)$

В заключение: когда . Отсюда следует, что вам нужно чтобы иметь постоянную вероятность нахождения любого цикла (не говоря уже о 4-цикле). $\Pr[E_q] = 1-o(1)$ $q=o(\sqrt{n})$ $\Omega(\sqrt{n})$

DW
источник

«Если k-й запрос является запросом проверки связности, то .» Я думаю ? (Даже если это так, то вывод еще проходит, конечно.)

P r [E k | E k - 1] \geq 1 - 1 / n

$Pr[Ek|Ek−1]≥1−1/n$

1 - 1 / \sqrt{n}

$1-1/\sqrt{n}$

усул

@usul, ой, да, спасибо! Исправлена.

Давайте предположим, что мы можем только запросить й край списка смежности данной вершины (который, я предполагаю, не отсортирован) или же смежные две заданные вершины. В этом случае нужно запросов, чтобы даже найти цикл. Это связано с тем, что существует вероятность что все наши запросы первого типа возвращают разные вершины, и что все наши запросы второго типа возвращают, что две вершины не связаны. $i$ $\sqrt n$ $1-o(1)$

Пожалуйста, поправьте меня, если я где-то ошибаюсь или неправильно понимаю проблему.

exfret
источник

Этот эскиз доказательства звучит для меня так, как будто он работает только для неадаптивных алгоритмов (т. Е. Запросов, исправленных заранее).

усул

@usul Почему это так? В любом случае, мы используем только одну ветвь дерева решений.

exfret

Возможно, я должен уточнить. Должно быть ясно, что если мы получим ответы на наши запросы в соответствии с предписаниями, то мы не сможем вывести 4-тактный цикл с постоянной вероятностью. Однако для любого дерева решений глубины существует вероятность нас отправят по такой ветке.

o (\sqrt{n})

$o(\sqrt n)$

1 - o (1)

$1-o(1)$

exfret

Спасибо! Я (несколько произвольно) принял другую конкретную версию, но, похоже, вы ее получили. Ценю ответ.

GMB

@GMB Я думаю, что вы приняли правильное решение; другой - гораздо более качественный ответ и заслуживает того, чтобы его увидели другие.

exfret