Pemeriksaan transitivitas vs. Penutupan Transitif

Apakah memeriksa transitivitas suatu digraf tidak lebih mudah daripada (dalam hal kompleksitas asimptotik) mengambil penutupan transitif dari digraf? Apakah kita tahu ada batas bawah yang lebih baik daripada untuk menentukan apakah digraf transitif atau tidak?$\Omega(n^2)$

Di bawah ini saya akan menunjukkan yang berikut: jika Anda memiliki algoritma waktu O ( ) untuk memeriksa apakah grafik transitif untuk , maka Anda memiliki O ( ) algoritma waktu untuk mendeteksi segitiga dalam grafik node, dan karenanya (dengan kertas dari FOCS'10 ) Anda akan memiliki algoritma waktu O ( ) untuk mengalikan dua boolean matriks, dan karenanya oleh hasil Fischer dan Meyer dari 70-an , ini juga menyiratkan algoritma waktu O ( ) untuk penutupan transitif.n 3 - ε ε > 0 n 3 - ε n n 3 - ε / 3 n × n n 3 - ε /$n^{3-\varepsilon}$$\varepsilon>0$$n^{3-\varepsilon}$$n$$n^{3-\varepsilon/3}$$n\times n$$n^{3-\varepsilon/3}$

Misalkan Anda ingin mendeteksi segitiga dalam simpul . Kita sekarang dapat membuat grafik berikut . adalah tripartit dengan partisi pada node masing-masing. Berikut setiap node dari memiliki salinan di bagian I , J , K . Untuk setiap tepi ( u , v ) dari G menambahkan tepi diarahkan ( u I , v J ) dan ( u Jn G H H I , J , K n x G x I , x J , x K G ( u I , v K$n$$G$$H$$H$$I,J,K$$n$$x$$G$$x_I,x_J,x_K$$I,J,K$$(u,v)$$G$$(u_I,v_J)$$(u_J,v_K)$. Untuk setiap nonedge ( u , v ) dari tambahkan tepi terarah .$(u,v)$$G$$(u_I,v_K)$

Pertama, jika mengandung segitiga , maka tidak transitif. Ini karena tepi berada di tetapi tidak. Kedua, jika tidak transitif, maka harus ada beberapa jalur diarahkan dari beberapa simpul untuk beberapa simpul di sehingga tidak tepi diarahkan di . Namun, jalur terpanjang di , maka membentuk segitiga diG u , v , w H ( u I , v J ) , ( v J , w K ) H ( u I , w K ) H s t H ( s , t ) H H 2 ( u I , v J ) , ( v J , w K ) ( u I$G$$u,v,w$$H$$(u_I,v_J),(v_J,w_K)$$H$$(u_I,w_K)$$H$$s$$t$$H$$(s,t)$$H$$H$ memiliki tepi, dan setiap jalur tersebut harus berbentuk dan tidak ada di$2$$(u_I,v_J),(v_J,w_K)$$(u_I,w_K)$$H$$u,v,w$$G$ .

Sepertinya adalah batas bawah yang paling dikenal, karena setiap batas bawah menyiratkan batas bawah untuk perkalian matriks boolean. Kita tahu bahwa pemeriksaan transitivitas dapat dicapai dengan menggunakan satu perkalian matriks boolean, yaitu, adalah transitif jika dan hanya jika .Ω ( n 2 ) G G = G $\Omega(n^2)$$G$$G = G^2$

Mencari tahu apakah DAG transitif sama sulitnya dengan memutuskan apakah digraf umum transitif (yang membawa kita kembali ke pertanyaan sebelumnya :)).

Asumsikan Anda memiliki algoritma yang berjalan dalam waktu O ( f ( n ) ) untuk memutuskan apakah DAG adalah transitif.$O(f(n))$

Diberi grafik G terarah , Anda dapat menggunakan algoritma acak berikut untuk memutuskan apakah G transitif dalam waktu O ( f ( n ) ⋅ log ( $G$$G$δ ))dan probabilitas kesalahan≤δ:$O(f(n)\cdot \log(\frac{1}{\delta}))$$\leq \delta$

 1. for $O(\log{\frac{1}{\delta}})$ iterations:

   1.1. Compute a random permutation on $V$. Denote the result by $<v_1,v_2,...,v_n>$.

   1.2. Set $G'=(V,E\cup \{(v_i,v_j)|i<j\})$ (i.e. compute a random acyclic orientation).

   1.3. If $G'$ (which is acyclic) is not transitive return false.

 2. return true.

Sekarang jelas bahwa jika G adalah transitif, algoritma ini mengembalikan true.$G$

Sekarang anggap G tidak transitif. Misalkan e 1 = ( v i , v j ) , e 2 = ( v j , v k ) ∈ E sedemikian rupa sehingga ( v i , v k ) ∉ E (harus ada tepi seperti G tidak transitif). Probabilitas bahwa e 1 , e 2 ∈ G ' adalah $G$$e_1=(v_i,v_j),e_2=(v_j,v_k)\in E$$(v_i,v_k)\notin E$$G$$e_1,e_2\in G'$6 , oleh karena itu dalam setiap iterasi probabilitas bahwa algoritma akan mencariGtidak transitif adalah$\frac{1}{6}$$G$6 dan setelahO(log(δ))iterasi probabilitas kegagalan paling banyakδ.$\frac{1}{6}$$O(\log{(\delta)})$$\delta$

Saya pikir ini harus layak dalam waktu linier, yaitu O ( n + m ) di mana n adalah jumlah simpul dan m jumlah tepi. Mungkin dengan mengadaptasi beberapa skema traversal grafik ke pengaturan yang diarahkan? Titik awal bisa berupa LexBFS / LexDFS yang dijelaskan di sini ; untuk grafik terarah tampaknya kita harus menggunakan pengurutan topologis daripada DFS, jadi mungkin itu mungkin dengan beberapa algoritma LexTSA untuk menemukan?$O(n+m)$$n$$m$

Mengenai jawaban sebelumnya, berikut adalah cara sederhana untuk mendefinisikan algoritma semacam itu. Tetapkan untuk setiap titik x indeks i ( x ) , diinisialisasi ke 0 . Untuk setiap x , misalkan M ( x ) menunjukkan multiset dari indeks dari tetangganya. Kami mensimulasikan penyortiran topologis dengan mempertahankan set R dari simpul yang belum dijelajahi, diinisialisasi ke seluruh set. Pada setiap langkah, kami melakukan hal berikut:$x$$i(x)$$0$$x$$M(x)$$R$

1. Memilih simpul x ∈ R yang multiset M ( x ) minimal (dalam urutan multiset);$x \in R$$M(x)$

2. Memperbarui i ( x ) loop counter dan menghapus saat x dari R .$i(x)$$x$$R$

Dapatkah algoritma ini digunakan untuk masalah Anda, atau untuk beberapa aplikasi lain?