Merekonstruksi pohon dari permintaan pemisah

Misalkan adalah pohon derajat konstan yang strukturnya tidak kita ketahui. Masalahnya adalah untuk mengeluarkan pohon dengan menanyakan pertanyaan dari formulir: "Apakah simpul terletak pada jalur dari simpul ke simpul ?". Asumsikan bahwa setiap permintaan dapat dijawab dalam waktu yang konstan oleh oracle. Kita tahu nilai , jumlah simpul di pohon. Tujuannya adalah untuk meminimalkan waktu yang dibutuhkan untuk menghasilkan pohon dalam hal .T x a b n $T$$T$$x$$a$$b$$n$$n$

Apakah ada algoritma untuk masalah di atas?$o(n^2)$

Asumsikan bahwa derajat dari setiap simpul dalam paling banyak 3.$T$

Apa yang saya tahu

Kasing berdiameter diameter mudah . Jika diameter pohon adalah , maka kita bisa mendapatkan algoritma divide-and-conquer:$D$

Setiap pohon biner memiliki pemisah yang baik yang membagi pohon menjadi komponen dengan ukuran tidak kurang dari 1 / 3n.

1. Pilih titik x. Jika itu label pemisah yang baik itu dan berulang.
2. Temukan semua 3 tetangga x.
3. Bergerak ke arah tetangga yang memiliki jumlah node terbesar. Ulangi Langkah 2 dengan tetangga.

Karena menemukan separator mengambil paling banyak langkah , kami mendapatkan algoritma .O ( n D log n $D$$O(nD\log n)$

Sebuah acak algoritma$O(n\;\log^2 n)$ . (dipindahkan dari komentar di bawah)

Pilih dua simpul x dan y secara acak. Dengan probabilitas 1/9 mereka akan berbaring di sisi yang berlawanan dari pemisah. Pilih simpul tengah jalur dari ke . Lihat apakah itu pemisah, jika tidak melakukan pencarian biner.$x$$y$

Dibutuhkan waktu yang diharapkan untuk menemukan pemisah. Jadi kami mendapatkan algoritma acak .O ( $O(n\;\log n)$$O(n\;\log^2 n)$

Latar Belakang. Saya belajar tentang masalah ini dari seorang teman yang bekerja dalam model grafis probabilistik. Masalah di atas kira-kira sama dengan mempelajari struktur pohon persimpangan menggunakan oracle yang, diberikan tiga variabel acak X, Y dan Z, dapat memberi tahu nilai informasi timbal balik antara X dan Y yang diberi nilai Z. Jika nilainya dekat ke nol, kita dapat mengasumsikan bahwa Z terletak pada jalur dari X ke Y.

Tidak . Strategi musuh sederhana berikut ini menyiratkan bahwa algoritma apa pun untuk merekonstruksi pohon -node membutuhkan setidaknya kueri "betweenness".$n$$\binom{n-1}{2} = n(n-1)/2$

Beri label secara acak pada node . Musuh menjawab semua pertanyaan seolah-olah pohon itu adalah bintang dengan titik di tengah; anggap sebagai root dan node lainnya sebagai anak-anaknya.0 $0,1,2,\dots,n-1$$0$$0$

Between?(a,x,b)
    if x=0 return TRUE else return FALSE

Sekarang anggaplah algoritma berhenti setelah melakukan kurang dari query. Maka harus ada dua simpul dan , tidak sama dengan nol, sehingga algoritme belum mempertanyakan permutasi rangkap tiga . Jika algoritme mengklaim bahwa pohon tersebut bukan bintang dengan pusat , musuh akan mengungkapkan inputnya, membuktikan bahwa algoritma tersebut salah. Musuh kemudian mengungkapkan bahwa sebenarnya adalah satu-satunya anak , membuktikan algoritma yang salah lagi.y z ( 0 , y , z ) 0 x $n(n-1)/2$$y$$z$$(0,y,z)$$0$$x$$y$

Pembaruan: Ups, cukup perhatikan batasan derajat. Untungnya, ini bukan rintangan utama. Ganti node dengan pohon biner favorit Anda, dengan node sebagai daun dalam urutan yang tidak diketahui, dan kemudian ungkapkan subtree ini ke algoritma rekonstruksi. Merekonstruksi hasil -node pohon biner masih membutuhkan setidaknya query. Secara ekuivalen, merekonstruksi pohon biner -node membutuhkan setidaknya query. (Saya yakin konstruksi yang lebih halus akan meningkatkan konstanta.)n - 1 ( 2 n - 3 ) n ( n - 1 ) / 2 m ( m + 3 ) ( m + 2 ) /$0$$n-1$$(2n-3)$$n(n-1)/2$$m$$(m+3)(m+2)/8$ Seperti yang ditunjukkan Jagadish, generalisasi ini tidak berfungsi; pertanyaan tentang node internal di pohon memaksakan pemesanan pada daun, yang mengurangi jumlah permintaan yang diperlukan.

$\tilde O(n \sqrt{n})$