Apakah ada algoritme untuk menjaga informasi keterhubungan secara efisien untuk DAG dengan adanya sisipan / penghapusan?

Dengan diberikan grafik asiklik terarah, , mungkinkah mendukung operasi berikut secara efisien?$G(V,E)$

• : Menentukan apakah ada jalur dalam G dari simpul a ke simpul$isConnected(G,a,b)$$G$$a$$b$
• : Menambahkan tepi dari a ke b dalam grafik$link(G,a,b)$$a$$b$$G$
• : Menghapus ujung dari a ke b di$unlink(G,a,b)$$a$$b$$G$
• : Menambahkan simpul ke G$add(G,a)$
• : Menghapus simpul dari G$remove(G,a)$

Beberapa catatan:

• Jika kita dianulir , tampaknya akan mudah untuk mempertahankan informasi keterhubungan, menggunakan struktur tipe data disjoint-set.$unlink$
• Jelas, dapat diterapkan menggunakan kedalaman atau pencarian luas-pertama, menggunakan representasi berbasis pointer naif grafik. Tetapi ini tidak efisien.$isConnected$

Saya berharap untuk waktu amortisasi konstan atau logaritmik untuk ketiga operasi. Apakah ini mungkin?

Masalah yang telah Anda jelaskan adalah kemampuan mencapai DAG sepenuhnya dinamis (juga disebut sebagai penutupan transitif sepenuhnya dinamis pada DAG). Ini disebut sepenuhnya dinamis karena orang juga mempelajari versi di mana hanya penghapusan yang mungkin (maka itu disebut reachremental reachability), dan di mana hanya insersi yang dimungkinkan (disebut incremental reachability).

Ada beberapa tradeoff antara waktu pembaruan dan waktu permintaan. Biarkan menjadi jumlah ujung dan n jumlah simpul. Untuk DAG, Demetrescu dan Italiano (FOCS'00) memberikan struktur data acak yang mendukung pembaruan (sisipan tepi atau penghapusan) dalam waktu O ( n 1,58 ) dan kueri keterjangkauan dalam waktu O ( n 0,58 ) waktu (sisipan / penghapusan simpul juga didukung , dalam O (1) waktu); hasil ini diperpanjang oleh Sankowski (FOCS'04) untuk bekerja untuk grafik diarahkan umum. Juga untuk DAG, Roditty (SODA'03) menunjukkan bahwa Anda dapat mempertahankan matriks penutupan transitif dalam total waktu O ( m n + I · n 2 + D ), di mana$m$$n$$n^{1.58}$$n^{0.58}$$mn+I·n^2+D$ adalah jumlah penyisipan, D jumlah penghapusan dan tentu saja waktu kueri adalah O ( 1 ).$I$$D$$1$

Untuk grafik berarah umum, waktu (pembaruan, kueri) berikut diketahui: (O ( ), O (1)) (Demetrescu dan Italiano FOCS'00 (diamortisasi), Sankowski FOCS'04 (kasus terburuk)), ( O ( m $n^2$ ),O($m\sqrt{n}$ )) (Roditty, Zwick FOCS'02), (O (m+nlogn), O (n)) (Roditty, Zwick STOC'04), (O (n 1,58 ), O (n 0,58 )) dan (O (n 1,495 ), O (n 1,495 )) oleh Sankowski (FOCS'04).$O(\sqrt{n}$$m+n\log n$$n$$n^{1.58}$$n^{0.58}$$n^{1.495}$$n^{1.495}$

Memperoleh waktu kueri polylogaritmik, tanpa menambah waktu pembaruan terlalu banyak adalah masalah besar yang terbuka, bahkan untuk DAG.

Saya pikir hasil terbaik sejauh ini dibahas dalam "Mantaining Dynamic Matriks untuk Fully Dynamic Transitive Closure" . Makalah itu membahas algoritma acak dengan waktu permintaan dan waktu pembaruan O ( n 1,58 ) .$O(n^{0.58})$$O(n^{1.58})$

(Ini hanya mencakup versi pertama dari pertanyaan Anda, dengan linkdan unlinktetapi tanpa adddan remove.)