Seberapa cepat kita bisa menghitung poset set inklusi dari set keluarga?

Mengingat satu set keluarga himpunan bagian dari alam semesta . Biarkan dan kami ingin menjawab adalah .$\mathcal{F}$$U$$S_1,S_2 \in \mathcal F$$S_1 \subseteq S_2$

Saya mencari struktur data yang memungkinkan saya untuk dengan cepat menjawab ini. Aplikasi saya adalah dari teori grafik di mana saya ingin melihat apakah menghapus sebuah simpul dan lingkungannya meninggalkan semua simpul yang terisolasi, dan untuk setiap daftar simpul semua simpul terisolasi yang ditinggalkannya.

Saya ingin membuat poset lengkap atau akhirnya tabel menyimpan false false dengan tepat set mana yang merupakan subset dari eachother.$|\mathcal{F}|^2$

Biarkan,dan, asumsikan$m = \sum_{S\in \mathcal{F}} |S|$$u = |U|$$n = |\mathcal{F}|$$u,n \leq m$

Kita dapat menghasilkan matriks kontainmen (grafik bipartit) dalam waktu dan kemudian dapat membuat tabel semua perbandingan dalam waktu dengan untuk setiap set , loop melalui semua elemen dari semua kelompok lain dan menandai ditetapkan sebagai bukan bagian dari jika mereka elemen tidak di . Total waktu .$n \times u$$O(un)$$n^2$$O(nm)$$S \in \mathcal{F}$$S$$S$$O(nm)$

Bisakah kita melakukan sesuatu dengan lebih cepat? Secara khusus, apakah waktu mungkin atau tidak?$O((n+u)^2)$

Saya menemukan beberapa artikel terkait:

Algoritma Sub-Quadratic Sederhana untuk Komputasi Subset Partial Order (1995) yang memberikan algoritma .$O(m^2 / log(m))$

Urutan Parsial Bagian: Komputasi dan Kombinatorik sedikit meningkatkan hal di atas tetapi juga mengklaim bahwa kertas di atas memecahkan masalah dalam waktu mana adalah jumlah maksimum set yang berbagi elemen yang sama, tetapi saya tidak dapat memahami hasil ini.$O(md)$$d$

Dalam artikel Antara danO ( n α$O(nm)$$O(n^{\alpha})$ O ( ( n + u ) 2.79 ) penulis menunjukkan bagaimana dalam grafik menemukan komponen yang terhubung setelah menghapus lingkungan tertutup dari sebuah simpul dengan menggunakan perkalian matriks. Ini dapat digunakan untuk menghitung set inklusi poset dengan menemukan semua komponen yang merupakan lajang dengan runtime .$O((n+u)^{2.79})$

Juga diskusi forum ini terkait: Apa cara tercepat untuk memeriksa set inklusi? yang menyiratkan batas bawah .$O(n^{2-\epsilon})$

Jika keacakan dibatasi, satu gagasan kasar adalah menghasilkan banyak fungsi "tanda tangan monoton acak" dan menggunakannya untuk memperkirakan hubungan subset (ala filter Bloom). Sayangnya, saya tidak tahu bagaimana membuatnya menjadi algoritma yang praktis, tetapi berikut adalah beberapa perkiraan yang tidak segera membuktikan bahwa ide itu tidak mungkin. Ini sangat jauh dari solusi yang berguna, tetapi saya akan menuliskannya jika itu membantu.

Asumsikan untuk kesederhanaan bahwa set semua ukurannya hampir sama, katakan , dan itu . Kita dapat mengasumsikan , jika tidak kita selesai. Tentukan Catat bahwa .s = o ( u ) 1 ≪ s $|S| = s \pm O(1)$$s = o(u)$$1 \ll s$p≫

$$\begin{aligned} q &= [s/2] \\ p &= \left[\frac{u \choose q}{s \choose q}\right] \end{aligned}$$ $p \gg 1$

Inilah bagian yang sangat tidak praktis. Pilih secara acak subset dengan penggantian, masing-masing ukuran , dan tentukan fungsi oleh iff untuk beberapa . Dengan diperbaiki dan bervariasi secara acak, kami telah Karena adalah monoton, menyiratkan$p$$A_1, \ldots, A_p \subset U$$q$$f : 2^U \to \{0,1\}$$f(S) = 1$$A_i \subset S$$i$$S$$A_i,f$

$$\begin{aligned} \Pr(f(S) = 0) &= \Pr(\forall i. A_i \not\subset S) \\ &= \Pr(A_1 \not\subset S)^p \\ &= \left(1 - {s \choose q}/{u \choose q}\right)^p \\ &= e^{-\Theta(1)} \end{aligned}$$ $f(S)$$S \subset T$$f(S) \le f(T)$ . Jika , perbaiki beberapa . Probabilitas bahwa mendeteksi adalah $T \not\subset S$$t \in T-S$$f$$T \not\subset S$ $$\begin{aligned} \Pr(f(S) = 0 < 1 = f(T)) &= \Pr(f(S) = 0) \Pr(f(T) = 1 | f(S) = 0) \\ &= e^{-\Theta(1)} \Pr(\exists i. A_i \subset T, A_i \cap T-S \ne 0 | f(S) = 0) \\ &= e^{-\Theta(1)} \Pr(\exists i. t \in A_i \subset T | f(S) = 0) \\ &\le e^{-\Theta(1)} \Pr(\exists i. t \in A_i \subset T) \\ &\approx e^{-\Theta(1)} p \Pr(t \in A_1 \subset T) \\ &\le e^{-\Theta(1)} p {s \choose q-1} / {u \choose q} \\ &\approx e^{-\Theta(1)} p \frac{q}{s-q} {s \choose q} / {u \choose q} \\ &= e^{-\Theta(1)} \end{aligned}$$ Beberapa dari langkah-langkah itu cukup renggang, tetapi saya tidak punya waktu untuk memperbaikinya malam ini. Bagaimanapun, jika mereka semua memegang, maka setidaknya itu tidak jelas tidak mungkin untuk secara acak menghasilkan fungsi tanda tangan yang memiliki kemungkinan masuk akal untuk membedakan subset dari non-subset. Sejumlah fungsi seperti itu kemudian akan membedakan semua pasangan dengan benar. Jika menghasilkan fungsi tanda tangan dan komputasi dapat dikurangi menjadi waktu, hasilnya akan menjadi keseluruhan algoritma .$f$$f(S)$$\tilde{O}(n+u)$$\tilde{O}(n^2+u^2)$

Bahkan jika perhitungan di atas benar, saya tidak tahu bagaimana cara menghasilkan fungsi tanda tangan monoton dengan fitur yang diinginkan dengan cepat. Kemungkinan juga teknik ini tidak mencakup ukuran set yang sangat berbeda.