Jak długo trwa znalezienie krótkiego cyklu na losowym wykresie?

Pozwolić $G \sim G(n, n^{-1/2})$ być losowym wykresem na $\approx n^{3/2}$ krawędzie Z bardzo dużym prawdopodobieństwem $G$ ma wiele $4$ motocykle. Naszym celem jest wyprodukowanie dowolnego z nich $4$ - motocykle tak szybko, jak to możliwe.

Załóżmy, że mamy dostęp do $G$ w formie listy sąsiedztwa możemy odnieść sukces ze stałym prawdopodobieństwem w $O(\sqrt{n})$ czas w następujący sposób: wybierz dowolny węzeł $v$ i zacznij generować losowo $2$ -ścieżki zaczynające się od $v$ ; kiedy znajdziemy dwa odrębne $2$ - ścieżki, które dzielą punkt końcowy, gotowe. Tam są $n$ możliwych punktów końcowych, a do paradoksu urodzinowego odniesiemy sukces ze stałym prawdopodobieństwem po odkryciu $\sqrt{n}$ z nich.

Czy możemy zrobić lepiej? W szczególności, czy możliwy jest algorytm o stałym czasie, który osiąga stałe prawdopodobieństwo?

— GMB
źródło

Wydaje mi się, że ten wykres ma zbyt mało krawędzi, aby mieć pożądaną właściwość, jeśli używasz standardowej terminologii, to jest jak

G (n, p)

$G(n,p)$ próbka z

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

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

— kodlu

Dzięki, masz rację, że miałem na myśli

p = n^{- 1 / 2}

$p = n^{-1/2}$ (edytowane). Te wykresy będą miały

C_{4}

$C_4$ s w dowolnym momencie współdzielenia dwóch węzłów

\geq 2

$\ge 2$ sąsiedzi, co dzieje się ze stałym prawdopodobieństwem na parę węzłów.

— GMB

Używam tutaj terminologii ( en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model ), w której każda krawędź jest uwzględniana niezależnie z prawdopodobieństwem

p

$p$ - więc krawędzi w oczekiwaniu.

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

$p \cdot {n \choose 2}$

— GMB,

Odpowiedzi:

Nie, nie możesz pokonać zapytań . Wyjaśnię, jak sformalizować szkic dowodowy tego exfret , w sposób, który działa w przypadku algorytmów adaptacyjnych. Wszystko to przewiduje odpowiedź exfret; Właśnie uzupełniam niektóre szczegóły. $\Theta(\sqrt{n})$

Rozważ dowolny (ewentualnie adaptacyjny) algorytm, który wydaje sekwencję zapytań, przy czym każde zapytanie albo „pobiera krawędź listy sąsiadujących wierzchołków ”, albo „sprawdza, czy wierzchołki są połączone krawędzią”. Możemy założyć, że żadne zapytanie nie jest powtarzane, ponieważ każdy algorytm, który je powtarza, może zostać przekształcony w taki, który nigdy nie powtarza żadnego zapytania. Podobnie możemy założyć, że algorytm nigdy nie wykonuje zapytania o połączenie na żadnej parze wierzchołków, o których wiadomo, że są połączone przez krawędź (a mianowicie, testowanie gdy zostało wcześniej zwrócone przez zapytanie pobierania na , lub było poprzednio zwrócone przez zapytanie pobierania w $i$ $v$ $v,w$ $v,w$ $w$ $v$ $v$ $w$ lub testowaliśmy wcześniej łączność ). $w,v$

Niech oznacza zdarzenie, że podczas pierwszych zapytań żaden wierzchołek jest zwracany przez więcej niż jedno zapytanie pobierania, a żadne zapytanie pobierania nie zwraca wierzchołka, który był poprzednio zapytany, i że żadne zapytanie testu połączenia nie zwraca „połączony” „. Udowodnimy, że jeśli . Wynika z tego, że żaden algorytm, który powoduje zapytania może mieć stałego prawdopodobieństwa znalezienia 4 cykli. $E_k$ $k$ $w$ $\Pr[E_q] = 1-o(1)$ $q=o(\sqrt{n})$ $o(\sqrt{n})$

Jak to udowodnimy? Obliczmy . Istnieją dwa przypadki: albo th zapytania to sprowadzić zapytanie, czy jest to zapytanie łączność test: $\Pr[E_k|E_{k-1}]$ $k$

Jeśli th zapytania to sprowadzić zapytanie na wierzchołek , istnieją wierzchołki wymienione wśród pierwszych zapytaniami, a jeśli th kwerenda zwraca jeden z tych, wtedy mamy , inaczej będziemy mieli . Teraz odpowiedź na te zapytanie jest równomiernie rozłożona na zestawie wierzchołków, gdzie zawiera wszystkie wierzchołki, które nie zostały zwrócone przez poprzednie zapytania pobierania na , więc odpowiedź na te zapytanie jest równomiernie rozłożona na zestawie o wielkości co najmniej $k$ $v$ $2(k-1)$ $k-1$ $k$ $\neg E_k$ $E_k$ $k$ $S$ $S$ $v$ $k$ $n-k+1$ . Prawdopodobieństwo trafienia co najmniej jednego z nich to , więc w tym przypadku . $\le 2(k-1)/(n-k+1)$ $\Pr[E_k|E_{k-1}] \ge 1 - 2(k-1)/(n-k+1)$
Jeśli p zapytanie jest zapytanie testu łączność, to . $k$ $\Pr[E_k|E_{k-1}] \ge 1 - 1/\sqrt{n}$

W obu przypadkach, jeśli mamy $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)}.$

Teraz,

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

Jeśli , to $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},$

więc

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

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

Prawa strona to w przybliżeniu . Gdy , jest to . $\exp \{ - 2q^2/(n-q)\}$ $q = o(\sqrt{n})$ $1 -o(1)$

Podsumowując: gdy . Wynika z tego, że potrzebujesz aby mieć stałe prawdopodobieństwo znalezienia dowolnego cyklu (nie mówiąc już o 4 cyklach). $\Pr[E_q] = 1-o(1)$ $q=o(\sqrt{n})$ $\Omega(\sqrt{n})$

— DW
źródło

„Jeśli k-te zapytanie jest zapytaniem testowym, to .” Myślę o ? (Nawet jeśli tak, wniosek nadal jest oczywisty.)

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

@usul, ups, tak, dziękuję! Naprawiony.

— DW,

Załóżmy, że możemy zapytać tylko tą krawędź listy przyległości danego wierzchołka (która, jak zakładam, nie jest posortowana) lub czy dwa podane wierzchołki sąsiadują. W takim przypadku powinno się zająć zapytań, aby nawet znaleźć cykl. Jest tak, ponieważ istnieje szansa że wszystkie nasze zapytania pierwszego typu zwracają różne wierzchołki i że wszystkie nasze zapytania drugiego typu zwracają, że dwa wierzchołki nie są połączone. $i$ $\sqrt n$ $1-o(1)$

Popraw mnie, jeśli gdzieś się mylę lub źle zrozumiałem problem.

— exfret
źródło

Ten szkic dowodu wydaje mi się, że działa tylko w przypadku algorytmów nieadaptacyjnych (tj. Zapytań ustalonych wcześniej).

— usul

@usul Dlaczego miałoby tak być? Whp używamy tylko jednej gałęzi drzewa decyzyjnego.

— exfret

Być może powinienem to wyjaśnić. Powinno być jasne, że jeśli otrzymamy odpowiedzi na nasze pytania zgodnie z zaleceniami, nie będziemy w stanie wygenerować 4-cykli ze stałym prawdopodobieństwem. Jednak dla każdego drzewa decyzyjnego o głębokości istnieje szansa że zostaniemy wysłani w dół takiej gałęzi.

o (\sqrt{n})

$o(\sqrt n)$

1 - o (1)

$1-o(1)$

— exfret

Dzięki! (Nieco arbitralnie) zaakceptowałem drugą rozwiniętą wersję, ale wygląda na to, że ją masz. Doceń odpowiedź.

— GMB

@GMB Myślę, że podjąłeś właściwą decyzję; drugi jest odpowiedzią o wiele lepszej jakości i zasługuje na to, aby inni go zobaczyli.

— exfret