Kompleksitas menghitung jarak rata-rata grafik

Biarkan menjadi jarak rata-rata dari grafik yang terhubung $\rm{ad}(G)$ $G.$

Salah satu cara untuk menghitung adalah dengan menjumlahkan elemen matriks jarak dan menskalakan jumlah dengan tepat. $\rm{ad}(G)$ $D(G),$ $G$

Jika grafik output adalah pohon maka diketahui bahwa jarak rata-rata dapat dihitung dalam waktu linier (Lihat B.Mohar, T.Pisanski - Cara menghitung indeks Wiener grafik). Tampaknya ada algoritma yang cepat untuk grafik dengan lebar pohon yang dibatasi juga.

Oleh karena itu pertanyaan yang menarik adalah, apakah membantu untuk mengetahuiDengan kata lain $D(G).$

Apakah mungkin untuk menghitung dalam waktu sub-kuadrat? $\rm{ad}(G)$

Yang saya tertarik ketahui adalah jika ada batas bawah teoretis mengapa hal ini tidak mungkin terjadi.

cc.complexity-theory graph-theory graph-algorithms Jernej
sumber

Seiring dengan hasil treewidth terikat yang Anda sebutkan (Cabello dan Knauer, "Algoritma untuk grafik treewidth terikat melalui pencarian rentang ortogonal", Komp. Geom. 2009) diketahui bagaimana menghitung ini dengan cepat untuk grafik yang secara geometri dapat ditanamkan dalam produk pohon Cartesian ( yang ternyata relevan untuk algoritma grafik kimia) - lihat Yeh dan Gutman, "Pada jumlah semua jarak dalam grafik komposit", Matematika Diskrit. 1994, dan Chepoi dan Klavžar, "Indeks Wiener dan indeks Szeged sistem benzenoid dalam waktu linier", JCICS 1997.

David Eppstein

Jawaban:

$O(n^{2-\delta})$ $\delta>0$ $\tilde{O}(n)$ $n$ $n$ $O(2^{(1-\varepsilon)n})$

Untuk membuktikan ini, perhatikan bahwa kami baru-baru ini membuktikan dalam (Algoritma perkiraan cepat untuk diameter dan jari-jari grafik yang jarang, Liam Roditty, V. Vassilevska Williams. STOC'13.) Bahwa jika seseorang dapat membedakan antara grafik diameter 2 dan 3 dalam subquadratic waktu, lalu SETH salah. Buktinya melalui pengurangan dari CNF-SAT. Pengurangan yang sama dapat digunakan untuk menunjukkan bahwa menghitung iklan (G) dalam waktu subquadratic menunjukkan bahwa SETH salah, karena jarak rata-rata dalam grafik dalam pengurangan adalah (di mana dan adalah jumlah node dan tepi dalam instance reduksi) jika instance CNF-SAT tidak memuaskan, dan lebih dari itu jika ada tugas yang memuaskan. $2-M/{N\choose 2}$ $N$ $M$

virgi
sumber