Apakah ada algoritma online untuk melacak komponen dalam grafik yang berubah tanpa arah?

12

Masalah

Saya memiliki grafik yang tidak terarah (dengan multi-edge), yang akan berubah seiring waktu, node dan edge dapat dimasukkan dan dihapus. Pada setiap modifikasi grafik, saya harus memperbarui komponen yang terhubung dari grafik ini.

Properti

Properti tambahan adalah bahwa tidak ada dua komponen yang akan dihubungkan kembali. Jelas, grafik dapat memiliki siklus ke jumlah yang sewenang-wenang (jika tidak solusinya akan sepele). Jika tepi tidak mengandung simpul , ia tidak akan pernah mengadopsi simpul itu. Namun, jika , itu dapat berubah menjadi .n n ∈ e n ∉ eenn∈en∉e

Pendekatan

Saya memiliki dua pendekatan yang mungkin sejauh ini, tetapi karena Anda akan melihat mereka mengerikan:

Negara-kurang lambat

Saya dapat mencari (dfs / bfs) grafik mulai dari elemen yang dimodifikasi setiap saat. Ini menghemat ruang, tetapi lambat karena kami memiliki O (n + m) untuk setiap modifikasi.

Pendekatan stateful fast (-er) (?)

Saya dapat menyimpan semua jalur yang mungkin untuk setiap node ke semua node yang mungkin, tetapi jika saya melihatnya dengan benar, ini akan mengambil memori O (n ^ 4). Tetapi saya tidak yakin bagaimana perbaikan runtime (jika ada satu sama sekali, karena saya harus menjaga informasi tetap up-to-hari untuk setiap node dalam komponen yang sama).

Pertanyaan

Apakah Anda memiliki petunjuk, bagaimana saya bisa belajar lebih banyak tentang masalah itu atau mungkin beberapa algoritma yang bisa saya bangun?

Catatan

Jika ada peningkatan besar dalam runtime / memori saya bisa hidup dengan solusi yang tidak optimal yang kadang-kadang mengatakan dua komponen adalah satu, tetapi tentu saja saya lebih suka solusi yang optimal.

ds.algorithms graph-theory approximation-algorithms online-algorithms bitmask
sumber
Jika saya membaca dua kalimat terakhir Anda di "Properti" dengan benar, maka tampaknya Anda hanya tertarik pada masalah dekremental. Jika demikian, pastikan untuk memeriksa karya Thorup tentang konektivitas dinamis decremental. (Anda dapat menemukan kutipan melalui petunjuk JeffE, yang merupakan versi masalah yang sepenuhnya dinamis.)
Maverick Woo
@Maverick Woo: Selalu ada tepi / node baru. Saya pikir properti terakhir tidak terlalu kuat, untuk alasan ini. Apakah masih memenuhi syarat sebagai decremental?
bitmask
Ups, saya tidak tahu bagaimana saya melewatkan kalimat pertama ... Lihat "jawaban" di bawah.
Maverick Woo

Jawaban:

17

Ada beberapa struktur data yang mendukung penyisipan tepi, penghapusan tepi, dan kueri konektivitas (Apakah dua simpul ini dalam komponen terhubung yang sama?) Dalam waktu polylogaritmik.

Jeffε
sumber
Kedengarannya luar biasa, begitu saya selesai membaca, saya kemungkinan besar akan menerima ini.
bitmask
6

Saya pikir Anda sedang mencari apa yang disebut algoritma grafik dinamis untuk dekomposisi komponen yang terhubung. Algoritma oleh Holm, de Lichtenberg dan Thorup [HLT01] telah diamortisasi waktu polylogarithmic pada setiap pembaruan tepi. Sudah lama sejak saya melihat masalah terakhir kali, jadi mungkin ada kemajuan yang lebih baru.

[HLT01] Jacob Holm, Kristian de Lichtenberg dan Mikkel Thorup. Algoritma penuh-dinamika deterministik penuh-polar-logaritmik untuk konektivitas, pohon spanning minimum, 2-edge, dan biconnectivity. Jurnal ACM , 48 (4): 723-760, Juli 2001. http://doi.acm.org/10.1145/502090.502095

Tsuyoshi Ito
sumber
Nasib sial. Kamu berhutang coke padaku.
Jeffε
@ Jeff Jeff: Saya tidak tahu tentang game itu . Tetapi menurut aturan, saya tidak kehilangan permainan (saya hanya dalam keadaan "sial"), jadi saya tidak berutang coke kepada Anda kecuali saya berbicara lebih jauh ... oh, tunggu sebentar.
Tsuyoshi Ito
andai saja Anda dapat memperdagangkan poin reputasi :)
Suresh Venkat
5

(Untuk sekarang izinkan saya tetap dengan pertanyaan konektivitas, yang sayangnya mungkin tidak cukup untuk aplikasi Anda.)

Banyak dari pekerjaan sebelumnya tentang masalah konektivitas dinamis ada dalam model pembaruan-tepi: Anda mengasumsikan jumlah simpul diperbaiki, dan Anda dapat menyisipkan dan / atau menghapus tepi saat membuat kueri. Jika Anda hanya bisa menyisipkan (menghapus), itu tambahan (decremental). Jika Anda dapat melakukan keduanya, itu sepenuhnya dinamis. Karya Thorup seperti yang ditunjukkan oleh JeffE (dan saya sendiri dalam komentar) semuanya untuk pembaruan terkini.

AFAIK, komunitas teori CS hanya mulai melihat pembaruan vertex untuk grafik umum. Ada pekerjaan yang luar biasa tentang hal ini oleh Chan, Pătraşcu, dan Roditty di FOCS 2008. Lihat tautan ini untuk revisi (September 2010) yang sangat baru dan referensi di dalamnya.

Maverick Woo
sumber
Mengapa Anda berpikir bahwa Holm et. Al. pendekatan tidak bekerja untuk masalah saya? Saya akan mengadopsinya.
bitmask
1
Jika grafik Anda memiliki tingkat terikat, maka secara teori Anda dapat meniru pembaruan vertex menggunakan sekelompok pembaruan tepi. Jika tidak, pembaruan simpul tunggal (misalnya, penghapusan pusat grafik bintang) dapat mengubah konektivitas grafik secara drastis, dan dalam hal ini Anda memerlukan hasil Chan et al.
Maverick Woo
Saya melihat. Saya seharusnya telah menyatakan dalam pertanyaan awal, bahwa penghapusan vertex jarang terjadi, jadi saya mampu melakukannya dari ujung ke ujung.
bitmask