Menghitung penyelesaian / jalur keberadaan oracle

Ada beberapa pertanyaan ( 1 , 2 , 3 ) tentang penyelesaian transitif di sini yang membuat saya berpikir jika sesuatu seperti ini dimungkinkan:

Asumsikan kita mendapatkan input diarahkan grafik dan ingin menjawab pertanyaan tipe " ?", Yaitu menanyakan apakah ada tepi antara dua simpul dalam penyelesaian transitif dari grafik ? (ekuivalen, "apakah ada jalur dari ke di ?").$G$$(u,v)\in G^+$$G$$u$$v$$G$

Asumsikan setelah diberikan Anda diizinkan untuk menjalankan preprocessing dalam waktu f ( n , m ) dan kemudian diminta untuk menjawab pertanyaan dalam waktu g ( n , m ) .$G$$f(n,m)$$g(n,m)$

Jelas, jika $f=0$ (yaitu tidak ada preprocessing diizinkan), yang terbaik yang dapat Anda lakukan adalah menjawab pertanyaan dalam waktu $g(n)=\Omega(n+m)$ . (jalankan DFS dari $u$ ke $v$ dan kembalikan true jika ada jalur).

Hasil sepele lainnya adalah bahwa jika $f=\Omega(min\{n\cdot m,n^\omega\})$ , Anda dapat menghitung penutupan transitif dan kemudian menjawab pertanyaan dalam $O(1)$ .

Bagaimana dengan sesuatu di tengah? Jika Anda diizinkan, katakanlah $f=n^2$ waktu preprocessing, dapatkah Anda menjawab pertanyaan lebih cepat dari $O(m+n)$ ? Mungkin meningkatkannya menjadi $O(n)$ ?

Variasi lain adalah: anggap Anda memiliki waktu preproses $poly(n,m)$ , tetapi hanya $o(n^2)$ ruang, dapatkah Anda menggunakan preprocessing untuk menjawab pertanyaan yang lebih efisien daripada ?$O(n+m)$

Bisakah kita mengatakan sesuatu secara umum tentang pengorbanan yang memungkinkan menjawab pertanyaan seperti itu?$f,g$

Struktur tradeoff yang agak mirip dipertimbangkan dalam sistem GPS, di mana memegang tabel perutean lengkap dari semua jarak berpasangan antara lokasi tidak layak sehingga menggunakan gagasan oracle jarak yang menyimpan tabel parsial tetapi memungkinkan percepatan permintaan yang signifikan atas perhitungan jarak keseluruhan grafik (biasanya menghasilkan hanya jarak yang diperkirakan antara titik).

Oracle reachability kompak ada untuk grafik planar,

Mikkel Thorup: Nubuat ringkas untuk jangkauan dan perkiraan jarak dalam digraf planar . J. ACM 51 (6): 993-1024 (2004)

tetapi "sulit" untuk grafik umum (bahkan grafik jarang)

Mihai Patrascu: Menyatukan Lansekap Batas Bawah Sel-Probe . SIAM J. Comput. 40 (3): 827-847 (2011)

Namun demikian, ada algoritma yang dapat menghitung pelabelan reachability mendekati optimal

Edith Cohen, Eran Halperin, Haim Kaplan, Uri Zwick: Reachability and Distance Queries via 2-Hop Labels . SIAM J. Comput. 32 (5): 1338-1355 (2003)

Maxim A. Babenko, Andrew V. Goldberg, Anupam Gupta, Viswanath Nagarajan: Algoritma untuk Optimalisasi Label Hub . ICALP 2013: 69-80

Membangun karya Cohen et al. dan yang lainnya, ada sedikit riset terapan (komunitas basis data) lihat mis

Ruoming Jin, Guan Wang: Oracle yang Sederhana, Cepat, dan Dapat Dicapai . PVLDB 6 (14): 1978-1989 (2013)

Yosuke Yano, Takuya Akiba, Yoichi Iwata, Yuichi Yoshida: Permintaan jangkauan yang cepat dan dapat diukur pada grafik dengan pemangkasan label dengan landmark dan jalur . CIKM 2013: 1601-1606

Saya akan menjawab pertanyaan Anda sebagian: tampaknya ada beberapa alasan mengapa konstruksi seperti itu mungkin sulit diperoleh.

$T(O(m),O(n))+n q(O(m),O(n))$$T(m,n)=O(n^2)$$q(m,n)=O(n)$$O(n^\omega)$$\omega=2$

$G$$n$$X,Y,Z,W$$v$$G$$v_X,v_Y,v_Z,v_W$$(u,v)$$G$$(u_X,v_Y),(u_Y,v_Z),(u_Z,v_W)$$T(O(m),O(n))$$v_X,v_W$$v$

$n^{2+o(1)}$