Jika diberi bobot, apakah ada algoritme O (V + E) untuk menggantikan setiap bobot dengan jumlah bobot leluhurnya?

Masalahnya, tentu saja, penghitungan ganda. Cukup mudah dilakukan untuk kelas DAGs tertentu = pohon, atau bahkan pohon paralel serial. Satu-satunya algoritma yang saya temukan yang bekerja pada DAG umum dalam waktu yang wajar adalah perkiraan (Synopsis difusion), tetapi meningkatkan ketepatannya adalah eksponensial dalam jumlah bit (dan saya perlu banyak bit).

Latar belakang: tugas ini dilakukan (beberapa kali dengan 'bobot' berbeda) sebagai bagian dari perhitungan probabilitas di BBChop (http://github.com/ealdwulf/bbchop) sebuah program untuk menemukan bug yang sebentar-sebentar (yaitu, versi bayesian dari ' git bisect '). Karenanya DAG yang dimaksud adalah riwayat revisi. Itu berarti bahwa jumlah tepi tidak mungkin mendekati kuadrat dari jumlah node, kemungkinan lebih kecil dari k kali jumlah node untuk beberapa k yang lebih kecil. Sayangnya saya belum menemukan properti berguna lainnya dari revisi DAG. Sebagai contoh, saya berharap bahwa komponen triconnected terbesar hanya akan tumbuh sebagai akar kuadrat dari jumlah node, tetapi sayangnya (setidaknya dalam sejarah kernel linux) ia tumbuh secara linear.

ds.algorithms graph-theory directed-acyclic-graph Ealdwulf
sumber

Hanya untuk memperjelas: hanya simpul yang memiliki bobot, bukan tepinya?

Heinrich Apfelmus

Ya, hanya simpulnya.

Ealdwulf

Ini sepertinya hampir duplikat dari cstheory.stackexchange.com/questions/553/… ?

Jukka Suomela

ini sebenarnya tampak lebih umum, karena menetapkan satuan bobot untuk semua simpul mengurangi masalah ini menjadi masalah jangkauan.

Suresh Venkat

Perkiraan tampaknya tidak sulit untuk dilakukan dengan beberapa faktor polylog tambahan ...

Sariel Har-Peled

Jawaban:

Kami berasumsi bahwa bobot titik dapat bilangan bulat positif acak, atau lebih tepatnya, mereka bisa bilangan bulat positif paling banyak 2 ⁿ . Maka tugas saat ini tidak dapat dilakukan bahkan dalam batas waktu O yang sedikit lebih lemah ( n ² ), kecuali jika penutupan transitif dari grafik yang diarahkan secara acak dapat dihitung dalam waktu O ( n ² ), di mana n menunjukkan jumlah simpul. (Perhatikan bahwa algoritma waktu O ( n ² ) untuk penutupan transitif akan menjadi terobosan.) Ini adalah kontrapositif dari klaim berikut:

Klaim . Jika tugas saat ini dapat dilakukan dalam waktu O ( n ² ), penutupan transitif dari grafik berarah yang diberikan sebagai matriks kedekatannya dapat dihitung dalam waktu O ( n ² ) (dengan asumsi beberapa model komputasi yang masuk akal).

Bukti . Sebagai preprocessing, kami menghitung dekomposisi komponen yang terhubung kuat dari graf berarah G yang diberikan dalam waktu O ( n ² ) untuk mendapatkan DAG G ′. Perhatikan bahwa jika kita dapat menghitung penutupan transitif G ', kita bisa merekonstruksi penutupan transitif G .

Sekarang tetapkan bobot 2 ⁱ untuk setiap simpul I DAG G ′ dan gunakan algoritma untuk masalah saat ini. Kemudian representasi biner dari penjumlahan yang ditugaskan untuk setiap simpul saya menggambarkan set leluhur i , dengan kata lain, kami telah menghitung penutupan transitif G ′. QED .

Kebalikan dari klaim tersebut juga berlaku: jika Anda dapat menghitung penutupan transitif DAG yang diberikan, mudah untuk menghitung jumlah yang dibutuhkan dengan pekerjaan tambahan dalam waktu O ( n ² ). Oleh karena itu, secara teori Anda dapat mencapai tugas saat ini dalam waktu O ( n ^2.376 ) dengan menggunakan algoritma untuk penutupan transitif berdasarkan pada algoritma penggandaan matriks Coppersmith-Winograd .

Sunting : Revisi 2 dan sebelumnya tidak menyatakan asumsi tentang kisaran bobot titik secara eksplisit. Per Vognsen menunjukkan dalam komentar bahwa asumsi implisit ini mungkin tidak masuk akal (terima kasih!), Dan saya setuju. Bahkan jika bobot arbitrer tidak diperlukan dalam aplikasi, saya kira jawaban ini mungkin mengesampingkan beberapa pendekatan dengan alasan berikut: “Jika pendekatan ini berhasil, itu akan memberikan algoritma untuk bobot arbitrer, yang dikesampingkan kecuali transitif Penutupan dapat dihitung dalam waktu O ( n ² ). "

Sunting : Revisi 4 dan sebelumnya menyatakan arah tepi salah.

Tsuyoshi Ito
sumber

Saya memikirkan hal ini tadi malam karena satu solusi praktis menggunakan vektor bit untuk melakukan penghitungan pengecualian. Saya kira satu-satunya pertanyaan adalah apakah masuk akal untuk menganggap bahwa bobot dapat memiliki panjang bit sebanding dengan n. Dalam prakteknya, saya bisa membayangkan bobot dibatasi oleh beberapa k sehingga jumlah maksimal yang mungkin adalah kn, yang tidak cukup bit untuk menarik trik ini.

Per Vognsen

@ Per: Saya setuju bahwa asumsi bahwa bobot titik bisa bilangan bulat n-bit mungkin dipertanyakan. Saya mengedit jawaban untuk membuat asumsi ini eksplisit. Terima kasih!

Tsuyoshi Ito

@ Per: Saya menyadari bahwa jika bobot titik adalah bilangan bulat yang dibatasi oleh O (1), masalahnya berkurang pada kasus di mana semua simpul memiliki bobot 1 dengan menduplikasi simpul dengan cara yang sesuai.

Tsuyoshi Ito

Sayangnya saya tidak melihat jawaban di utas itu untuk masalah penghitungan. Hitungan mengandung informasi logaritmik lebih sedikit daripada daftar penutupan transitif, O (n log n) vs O (n ^ 2), jadi saya tidak melihat bagaimana pengurangan langsung bisa bekerja.

Per Vognsen

Omong-omong, versi yang menarik dari masalah ini adalah ketika kita terikat pada faktor cabang dan informasi tentang pertumbuhan ukuran generasi (a la jenis topologi) dari DAG. Jika pertumbuhannya eksponensial, polanya pada dasarnya seperti pohon. Bagaimana jika itu linear, log-linear, kuadratik, dll?

Per Vognsen

Ini adalah perluasan dari komentar saya tentang jawaban Tsuyoshi. Saya pikir jawaban negatif untuk pertanyaan dapat dibuat tanpa syarat.

$\omega(n)$ $O(n)$

$G_{r,c}$ $r \times c$ $r$ $r$ $c$

$r = (\log\ n)/2$ $c = 2n/\log\ n$

$\sqrt{n}$ $\omega(\log\ n)$

$\omega(n)$ $2c(r-1) = O(n)$

Intinya tampaknya bahwa urutan parsial yang mendasarinya padat, tetapi DAG mewakili reduksi transitifnya, yang bisa jarang.

András Salamon
sumber

Argumen ini menarik, tetapi saya tidak yakin apakah ini dapat dijadikan bukti dari pernyataan yang menarik. Mempertimbangkan kesulitan yang meluas untuk membuktikan batas masalah yang lebih rendah, argumen ini tampaknya mudah bagi saya.

Tsuyoshi Ito

@ Tsuyoshi: Saya pikir keberadaannya harus bekerja melalui argumen probabilistik, dan batas bawahnya lemah sehingga sepertinya ada cukup ruang untuk itu bekerja. Tetapi Anda benar, ini adalah handwavy, bahwa frasa "penambahan yang tidak dapat digunakan kembali rata-rata" membutuhkan fondasi yang lebih baik.

András Salamon

-2

Ini salah dan didasarkan pada kesalahpahaman pada pertanyaan. Terima kasih kepada Tsuyoshi karena dengan sabar menunjukkan kesalahan saya. Berangkat jika orang lain melakukan kesalahan yang sama.

$k$

$k$ $O(k|V|)$

$O(|V|+|E|)$

Pendekatan ini juga harus bekerja dengan baik jika ada beberapa node dengan banyak pendahulu langsung, selama mereka relatif jarang.

András Salamon
sumber

Saya tidak mengerti. Bagaimana Anda menghindari penghitungan ganda ketika DAG bukan pohon? Bahkan, jika saya tidak salah, kasus umum dapat dikurangi menjadi kasus di mana setiap titik memiliki paling banyak dua pendahulu, dan setiap algoritma waktu-linear untuk kasus terakhir memberikan algoritma garis-waktu untuk kasus umum.

Tsuyoshi Ito

O (| V | + | E |)

$O(|V|+|E|)$

k

$k$

Saya khawatir Anda salah memahami komentar saya. Saya mempertanyakan kebenaran algoritma Anda, bukan waktu berjalan. Misalkan DAG dengan empat simpul A, B, C, D dengan tepi A → B → D dan A → C → D dengan setiap simpul diberi bobot. Setelah menghitung jumlah parsial untuk B dan C, Anda tidak bisa hanya menambahkan jumlah parsial untuk B dan C untuk menghitung jumlah untuk D karena melakukan hal itu akan menambah bobot dari simpul A dua kali.

Tsuyoshi Ito

\sum_{u < v} w (u)

$\sum_{u < v} w(u)$

Iya nih. Dan sekarang saya ingat bahwa pertama kali saya melihat pertanyaan ini, saya salah membaca pertanyaan itu dengan cara yang sama dan berpikir itu akan jelas. Tapi tidak, pertanyaan sebenarnya lebih sulit dari itu. Waktunya berpikir….

Tsuyoshi Ito