Merutekan keberadaan antara n pasang node

Diberikan grafik asiklik terarah dengan simpul bagaimana kita dapat menentukan apakah ada jalur antara n pasangan simpul berikut ( 1 → n + 1 ) , … , ( n → n + n ) ? Ada algoritma sederhana dalam O ( n ⋅ ( n + m ) ) (di mana m adalah jumlah tepi) dengan melakukan pencarian dari setiap node 1 ... n , tetapi dapatkah itu dilakukan lebih baik?$2n$$(1 \rightarrow n+1), \ldots, (n \rightarrow n+n)$$O(n \cdot (n + m))$$1 \ldots n$

EDIT: Saya mencari keberadaan, bukan jalur lengkap.

Seperti yang ditunjukkan Chandra Chekuri dalam komentar, Anda bisa menghitung penutupan transitif melalui perkalian matriks cepat, menyelesaikan masalah dalam waktu O ( ) (gunakan metode favorit Anda, O ( n 2.376 ) melalui Coppersmith dan Winograd, atau lebih praktisnya menggunakan Strassen's O ( n 2.81 )), dan ini akan bagus untuk grafik yang padat.$n^\omega$$n^{2.376}$$n^{2.81}$

Sekarang, saya mengklaim bahwa jika Anda dapat mengalahkan waktu berjalan ini untuk masalah Anda untuk grafik padat, Anda akan mendapatkan algoritma untuk deteksi segitiga yang lebih efisien daripada menghitung produk dari dua matriks Boolean. Keberadaan algoritma semacam itu adalah masalah terbuka utama.

Saya akan mengurangi masalah segitiga menjadi masalah jangkauan-n-pasangan-DAG. Misalkan kita diberi grafik G pada n node dan kami ingin menentukan apakah G berisi segitiga.

Sekarang, dari G buat DAG G 'sebagai berikut. Buat empat salinan set simpul, , V 2 , V 3 , V 4 . Untuk salinan u i ∈ V i , v i + 1 ∈ V i + 1 untuk i = 1 , 2 , 3 , tambahkan tepi ( u i , v i + 1 ) iff ( u , v $V_1$$V_2$$V_3$$V_4$$u_i\in V_i$$v_{i+1}\in V_{i+1}$$i=1,2,3$$(u_i,v_{i+1})$$(u,v)$berada di G. Sekarang jika kita bertanya apakah ada jalur antara salah satu pasangan untuk semua u ∈ G, maka ini akan persis bertanya apakah ada segitiga di G . Grafik saat ini memiliki 4 n node dan kami bertanya tentang n pasangan. Namun, kita dapat menambahkan 2 n node dummy terisolasi dan memiliki 3 n query (dengan menambahkan query untuk 2 n pasangan yang berbeda ( y , d ) di mana y ∈ V $(u_1, u_4)$$u\in$$G$$4n$$n$$2n$$3n$$2n$$(y,d)$ dan d boneka), sehingga mendapatkaninstance 6 n -node dari masalah Anda.$y\in V_2\cup V_3$$d$$6n$

Sortasi topologis ( ) kemudian turunkan dengan menyebarkan bit bit dari mana setiap node dapat dicapai ( O ( m n ) ).$O(m+n)$$O(m n)$

$O(n)$$n+x$$x$$x$$n+x$

$O(N^2)$

yespath = array(1..N)       // output of the algorithm
                            // initially filled with false
processed = array(1..N)     // processed nodes

// HEURISTIC 1: some preprocessing
for every node u in 1..N
  if (no outbound edges from u) then processed[u] = true
  if (no inbound edges to u+N) then processed[u] = true

for each node u in [1..N]    // MAIN loop 
  if (not processed[u]) then
    collected = [u]          // a list that initially contains u
    visited = array(1..2*N)  // filled with zeroes        
    do a breadth first scan from u
       for each node v found in the search
         set visited[v] = distance from u
         if (v <= N) then add v to collected
    end do

    // HEURISTIC 2: useful collected info on other nodes <= N
    foreach node v in collected
      processed[v] = true
      if ( visited[ v + N ] > 0 and visited[v] < visited[v+N] ) then yespath[v] = true
    end foreach

  end if
end for // MAIN loop

$O(N^2)$$O(N*k)$$e > u + N$

Heuristik lain dapat ditambahkan, tetapi efisiensinya (dan efisiensi dari tiga yang diusulkan) sangat tergantung pada struktur grafik.