Algoritma untuk menemukan semua daftar tetangga 2-hop dalam grafik

Diberikan grafik , di mana . Apa yang dimaksud dengan algoritma cepat untuk menghasilkan koleksi semua daftar lingkungan 2-hop dari semua node di . $G = (V,E)$ $|V| = n$ $V$

Secara naif, Anda dapat melakukannya di . Dengan kekuatan matriks, Anda dapat melakukannya dengan menggunakan algoritma Strassen. Anda bisa melakukan lebih baik dari ini menggunakan algoritma penggandaan matriks lain. Adakah metode yang lebih baik? Adakah algoritma Las Vegas? $O(n^3)$ $O(n^{2.8})$

algorithms algorithm-analysis graphs randomized-algorithms Dipotong
sumber

Ada algoritma deterministik O (n ^ 2).

Mike G

@ MikeG bagaimana melakukannya?

AJed

@MikeG telah menemukan algoritma multiplikasi matriks kuadratik waktu yang luar biasa yang sayangnya terlalu kecil untuk ditampung dalam komentar

stackexchange

@SashoNikolov Bisakah Anda memberikan referensi?

Raphael

Jawaban:

Pertanyaannya benar-benar tergantung pada apa definisi tepat dari 2-hop. Jika dengan 2-hop yang Anda maksud adalah himpunan maka jawaban saat ini adalah tidak, Anda tidak dapat melakukannya lebih cepat daripada mana adalah konstanta yang biasa dikaitkan dengan kompleksitas melakukan produk matriks.

h p (v) = {u ∣ there is a path of length 2 between u and v},

$hp(v) = \{ u \mid \mbox{there is a path of length 2 between u and v}\},$

O (n^{ω})

$O(n^{\omega})$

ω

$\omega$

Mengapa? Untuk setiap simpul periksa apakah berdekatan dengan simpul dalam $v$ $v$ $hp(v).$ Jika demikian, Anda telah menemukan segitiga di grafik Anda. Apalagi grafiknya adalah segitiga bebas jika Anda tidak menemukan titik $v$ dengan properti ini.

Algoritma yang paling dikenal saat ini untuk menguji apakah grafik bebas segitiga memiliki kompleksitas waktu $O(n^{\omega}).$

Jernej
sumber

Menarik, apakah Anda memiliki referensi untuk masalah pengenalan bebas segitiga. Apakah ada batas bawah yang terbukti untuk masalah ini?

AJed

Tidak ada batas bawah yang terbukti tetapi baru-baru ini, koneksi yang sangat mengejutkan ditemukan. Jika Anda dapat mendeteksi segitiga lebih cepat dari

O (n^{ω})

$O(n^{\omega})$ maka Anda dapat menghitung produk matriks lebih cepat dari

O (n^{ω})

$O(n^{\omega})$ . Lihat kertas "Triangle Detection Versus Multiplication Matrix: Sebuah studi tentang Reducibility Subcubic Benar-benar" oleh Williams dan Williams. Di sini kam.mff.cuni.cz/~matousek/cla/tria-mmult.pdf

Jernej

Rapi, senang itu membantu!

Jernej