Pengurangan DAG secara transitif

Saya mencari algoritma O (V + E) untuk menemukan reduksi transitif yang diberikan DAG.

Yaitu menghapus sebanyak mungkin tepi sehingga jika Anda dapat mencapai v dari Anda, untuk v dan Anda sewenang-wenang, Anda masih dapat mencapai setelah menghilangkan tepi.

Jika ini adalah masalah standar, tunjukkan saya solusi model.

Kita dapat menyelesaikan masalah ini hanya dengan melakukan DFS dari setiap titik.

1. Untuk setiap simpul , mulai DFS dari setiap simpul v sehingga v adalah turunan langsung dari u , yaitu. ( u , v ) adalah keunggulan.$u \in G$$v$$v$$u$$(u,v)$
2. Untuk setiap simpul dapat dijangkau oleh DFS dari v , lepaskan ujungnya ( u , v ′ ) .$v'$$v$$(u, v')$

Kompleksitas keseluruhan di atas adalah kompleksitas menjalankan DFS ', yaitu O ( N ( N + M ) ) .$N$$O(N(N+M))$

Bukan yang Anda cari. Tetapi hanya untuk tujuan berbagi pengetahuan, Anda dapat melakukannya dengan pesan jika Anda menganggap bahwa setiap titik bertindak sebagai prosesor . Perhatikan bahwa setiap titik memiliki nilai yang sebanding. Oleh karena itu, ada beberapa simpul sehingga mereka lebih besar dari semua tetangga mereka. Verteks ini melakukan hal berikut:$O(|E|)$

1. Biarkan menjadi tetangga maksimum yang lebih kecil dari v ,$u$$v$
2. mengirim pesan ke dan menyertakan edge ( v , u ) dalam output.$u$$(v,u)$
3. Untuk setiap tetangga dari u dan v (dan lebih kecil dari keduanya), jangan masukkan ( v , w ) dalam output.$w$$u$$v$$(v,w)$
4. Ulangi langkah-langkah sampai semua tepi untuk tetangga yang lebih kecil v ′ dari vertex v dimasukkan atau tidak termasuk dalam output.$(v,v')$$v'$$v$

Sekarang jika sebuah simpul menerima pesan dari setiap tetangga yang lebih besar (yaitu semua tepi ( v ′ , v ) termasuk atau tidak termasuk, maka simpul v bertindak seolah-olah itu adalah yang terbesar di lingkungannya. Yaitu, ia melakukan 4 langkah yang disebutkan sebelumnya.$v$$(v',v)$$v$

Algoritma ini berakhir pada pesan di lingkungan terdistribusi. Saya tahu ini bukan yang Anda minta.$O(|E|)$

Lemma: Jika ada tepi V -> Y dan Y juga merupakan penerus tidak langsung dari V, (misalnya, V -> W -> + Y) maka tepi V -> Y adalah transitif dan bukan bagian dari akar transitif.

Metode: Melacak penutupan transitif dari setiap simpul, bekerja dari terminal ke simpul awal dalam urutan topologi terbalik. Himpunan penerus tidak langsung dari V adalah penyatuan dari penutupan transitif dari penerus langsung dari V. Penutupan transitif dari V adalah penyatuan dari penerus tidak langsung dan penerus langsungnya.

Algoritma:

    Initialise Visited as the empty set.
    For each vertex V of G, 
        Invoke Visit(V).

    Visit(V):
        If V is not in Visited,
            Add V to Visited, 
            Initialise Indirect as the empty set,
            For each edge V -> W in G,
                Invoke Visit(W),
                Add Closure(W) to Indirect.
            Set Closure(V) to Indirect.
            For each edge V -> W in G,
                Add W to Closure(V),
                If W is in the set Indirect,
                    Delete the edge V -> W from G.

Ini mengasumsikan bahwa Anda memiliki beberapa cara yang efisien untuk melacak set simpul (misalnya, peta bit), tetapi saya pikir asumsi ini dibuat dalam algoritma O (V + E) lainnya juga.

Efek samping yang berpotensi berguna adalah ia menemukan penutupan transitif dari setiap simpul G.

Saya memecahkan masalah yang sama tetapi itu tidak persis sama. Ia meminta minimum tidak ada tepi dalam grafik setelah pengurangan sedemikian rupa sehingga simpul yang awalnya terhubung masih terhubung dan tidak ada koneksi baru dibuat. Karena jelas, ia tidak mengatakan untuk menemukan grafik yang diperkecil, tetapi berapa banyak tepi redundan yang ada. Masalah ini dapat diselesaikan di O (V + E). Tautan ke penjelasan adalah https://codeforces.com/blog/entry/56326 . Tapi saya pikir untuk membuat grafik sebenarnya, itu akan memiliki kompleksitas tinggi daripada O (N)