Berapa lama untuk menemukan siklus pendek dalam grafik acak?

Biarkan menjadi grafik acak pada tepi. Dengan probabilitas sangat tinggi, memiliki banyak sepeda. Tujuan kami adalah untuk menghasilkan salah satu dari - sepeda ini secepat mungkin. $G \sim G(n, n^{-1/2})$ $\approx n^{3/2}$ $G$ $4$ $4$

Andaikata kita memiliki akses ke dalam bentuk daftar adjacency, kita dapat berhasil dengan probabilitas konstan dalam waktu sebagai berikut: pilih sembarang simpul dan mulailah menghasilkan jalur acak mulai dari ; setelah kami menemukan dua jalur berbeda yang berbagi titik akhir, kami selesai. Ada kemungkinan titik akhir, dan dengan paradoks ulang tahun kita akan berhasil dengan probabilitas konstan setelah menemukan tentang dari mereka. $G$ $O(\sqrt{n})$ $v$ $2$ $v$ $2$ $n$ $\sqrt{n}$

Bisakah kita berbuat lebih baik? Secara khusus, apakah algoritma waktu-konstan yang berhasil dengan probabilitas konstan mungkin?

graph-theory graph-algorithms property-testing random-graphs GMB
sumber

Bagiku grafik ini memiliki terlalu sedikit tepi untuk memiliki properti yang Anda inginkan, jika Anda menggunakan terminologi standar, itu seperti sampel dengan

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})$

kodlu

Terima kasih, Anda benar yang saya maksud (diedit). Grafik ini akan memiliki s kapan saja dua node berbagi tetangga, yang terjadi dengan probabilitas konstan per pasangan node.

p = n^{- 1 / 2}

$p = n^{-1/2}$

C_{4}

$C_4$

\geq 2

$\ge 2$

GMB

Saya menggunakan terminologi di sini ( en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model ), di mana setiap sisi disertakan secara independen dengan probabilitas - jadi, tepi harapan.

p

$p$

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

$p \cdot {n \choose 2}$

GMB

Jawaban:

Tidak, Anda tidak dapat mengalahkan kueri . Saya akan menjelaskan bagaimana memformalkan sketsa bukti exfret tentang ini, dengan cara yang bekerja untuk algoritma adaptif. Ini semua diantisipasi dalam jawaban exfret; Saya hanya mengisi beberapa detail. $\Theta(\sqrt{n})$

Pertimbangkan algoritme apa pun (yang mungkin adaptif) yang mengeluarkan urutan kueri, di mana setiap kueri "mengambil tepi ke- dari daftar kedekatan vertex " atau "menguji apakah simpul terhubung oleh tepi". Kita dapat mengasumsikan bahwa tidak ada kueri yang diulang, karena algoritma apa pun yang mengulangi kueri dapat diubah menjadi kueri yang tidak pernah mengulangi kueri apa pun. Demikian pula, kita dapat mengasumsikan bahwa algoritma tidak pernah melakukan permintaan konektivitas pada setiap pasangan simpul yang sudah dikenal untuk dihubungkan dengan sebuah sisi (yaitu, menguji saat sebelumnya dikembalikan oleh pengambilan query pada , atau adalah sebelumnya dikembalikan oleh kueri pengambilan di $i$ $v$ $v,w$ $v,w$ $w$ $v$ $v$ $w$ , atau sebelumnya kami menguji konektivitas ). $w,v$

Biarkan menunjukkan peristiwa bahwa, selama kueri pertama , tidak ada simpul dikembalikan oleh lebih dari satu permintaan-kuambil, dan tidak ada permintaan-ku mengembalikan sebuah simpul yang sebelumnya queried, dan bahwa tidak ada konektivitas-tes-permintaan kembali "terhubung ". Kami akan membuktikan bahwa jika . Oleh karena itu, tidak ada algoritma yang membuat kueri dapat memiliki probabilitas konstan untuk menemukan 4 siklus. $E_k$ $k$ $w$ $\Pr[E_q] = 1-o(1)$ $q=o(\sqrt{n})$ $o(\sqrt{n})$

Bagaimana kita membuktikan ini? Mari menghitung . Ada dua kasus: kueri adalah kueri pengambilan, atau kueri uji konektivitas: $\Pr[E_k|E_{k-1}]$ $k$

Jika kueri th adalah kueri pengambilan pada vertex , ada simpul yang disebutkan di antara kueri pertama , dan jika kueri th mengembalikan salah satu dari itu maka kita akan memiliki , jika tidak kita akan memiliki . Sekarang respons terhadap permintaan didistribusikan secara seragam pada set dari simpul, di mana berisi semua simpul yang belum dikembalikan oleh pengambilan kueri sebelumnya pada , sehingga respons terhadap permintaan ke- didistribusikan secara seragam pada satu set ukuran setidaknya $k$ $v$ $2(k-1)$ $k-1$ $k$ $\neg E_k$ $E_k$ $k$ $S$ $S$ $v$ $k$ $n-k+1$ . Peluang untuk memukul setidaknya satu di antaranya adalah , jadi dalam kasus ini, . $\le 2(k-1)/(n-k+1)$ $\Pr[E_k|E_{k-1}] \ge 1 - 2(k-1)/(n-k+1)$
Jika kueri adalah kueri uji konektivitas, maka . $k$ $\Pr[E_k|E_{k-1}] \ge 1 - 1/\sqrt{n}$

Dalam kedua kasus, jika kita miliki $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)}.$

Sekarang,

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

Jika , maka $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},$

begitu

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

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

Sisi kanan kira-kira . Ketika , ini adalah . $\exp \{ - 2q^2/(n-q)\}$ $q = o(\sqrt{n})$ $1 -o(1)$

Kesimpulannya: ketika . Oleh karena itu, Anda memerlukan untuk memiliki probabilitas konstan untuk menemukan siklus apa pun (apalagi siklus 4). $\Pr[E_q] = 1-o(1)$ $q=o(\sqrt{n})$ $\Omega(\sqrt{n})$

DW
sumber

"Jika kueri k adalah kueri uji konektivitas, maka ." Saya berpikir ? (Bahkan jika demikian, kesimpulannya tetap berjalan tentu saja.)

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, oops, ya, terima kasih! Tetap.

Mari kita asumsikan kita hanya bisa query th tepi daftar adjacency simpul tertentu (yang saya mengasumsikan tidak diurutkan) atau apakah dua simpul diberikan berdekatan. Dalam hal ini, ia harus mengambil kueri untuk menemukan siklus. Ini karena ada peluang bahwa semua kueri kami dari tipe pertama mengembalikan simpul yang berbeda dan bahwa semua kueri kami dari tipe kedua mengembalikan bahwa kedua simpul tidak terhubung. $i$ $\sqrt n$ $1-o(1)$

Harap perbaiki saya jika saya salah atau salah paham masalah.

mengeluarkan
sumber

Sketsa bukti ini kedengarannya seperti hanya berfungsi untuk algoritme nonadaptif (mis. Kueri yang diperbaiki sebelumnya).

usul

@ Usul Mengapa demikian? Pokoknya kita hanya menggunakan satu cabang pohon keputusan.

exfret

Mungkin saya harus mengklarifikasi. Seharusnya jelas bahwa jika kita menerima jawaban atas pertanyaan kita sebagaimana ditentukan maka kita tidak dapat menghasilkan 4 siklus dengan probabilitas konstan. Namun, untuk setiap pohon keputusan dengan kedalaman ada kemungkinan kami dikirim ke cabang seperti itu.

o (\sqrt{n})

$o(\sqrt n)$

1 - o (1)

$1-o(1)$

exfret

Terima kasih! Saya (agak sewenang-wenang) menerima versi yang lebih baik tetapi sepertinya Anda mendapatkannya. Hargai responsnya.

GMB

@ GMB Saya pikir Anda membuat keputusan yang benar; yang lain adalah jawaban berkualitas jauh lebih tinggi dan pantas untuk dilihat pertama oleh orang lain.

exfret