Diberikan grafik, putuskan apakah konektivitas tepinya setidaknya n / 2 atau tidak

13

Bab 1 buku Metode Probabilistik, oleh Alon dan Spencer menyebutkan masalah berikut:

Diberikan grafik , putuskan apakah konektivitas tepinya setidaknya n / 2 atau tidak.Gn/2

Penulis menyebutkan adanya sebuah algoritma oleh Matula dan meningkatkan ke O ( n 8 / 3 log n ) .O(n3)O(n8/3logn)

Pertanyaan saya adalah, apa waktu berjalan paling dikenal untuk masalah ini?

Biarkan saya menggambarkan algoritma yang ditingkatkan.

Pertama, putuskan apakah memiliki tingkat minimum setidaknya n / 2 atau tidak. Jika tidak, maka konektivitas tepi jelas kurang dari n / 2 .Gn/2n/2

Selanjutnya, jika bukan itu masalahnya, hitung himpunan dominan dari G ukuran O ( log n ) . Ini dapat dilakukan dalam waktu O ( n 2 ) , dengan suatu algoritma yang dijelaskan dalam bagian buku sebelumnya.UGO(logn)O(n2)

Selanjutnya, ia menggunakan hal-hal berikut yang tidak terlalu sulit untuk membuktikan fakta:

Jika derajat minimum adalah , maka untuk setiap pemotongan tepi paling banyak δ yang membagi V menjadi V 1 dan V 2 , setiap rangkaian G yang mendominasi harus memiliki simpulnya dalam V 1 dan V 2 .δδVV1V2GV1V2

Sekarang perhatikan himpunan dominan . Sejak G memiliki minimal gelar n / 2 , setiap potong tepi ukuran kurang dari n / 2 juga harus memisahkan U . Jadi untuk setiap i { 2 , k } , kami menemukan ukuran potongan tepi terkecil yang memisahkan u 1 dan u i . Masing-masing dari hal-hal ini dapat dilakukan dalam waktu O ( n 8 / 3U={u1,,uk}Gn/2n/2Ui{2,k}u1ui menggunakan algoritma max-flow. Jadi total waktu yang diambil adalah O ( n 8 / 3 log n ) .O(n8/3)O(n8/3logn)

Vinayak Pathak
sumber
Btw, tentu saja peningkatan dalam algoritma max-flow akan mengarah ke peningkatan di sini juga. Tapi kurasa adalah algoritma max-aliran yang paling dikenal saat ini? O(n8/3)
Vinayak Pathak
Mungkin saya salah mengerti sesuatu, tetapi bukankah algoritma mincut acak Karger-Stein telah menjalankan waktu ? O~(n2)
Sasho Nikolov
2
Apakah waktu berjalan yang diharapkan? Algoritma yang saya jelaskan sepenuhnya deterministik. O(n2)
Vinayak Pathak
3
Algoritma ini adalah Monte Carlo: selalu lengkap dalam waktu dan mengeluarkan potongan minimum dengan probabilitas tinggi. Probabilitas kegagalan tergantung terbalik pada waktu berjalan, tentu saja. Maaf, mengingat bahwa kutipan Anda adalah Alon-Spencer, saya hanya berasumsi bahwa algoritma ini diacak :)O~(n2)
Sasho Nikolov
Jika Anda mencari algoritma deterministik saya pikir Anda harus menentukan itu dalam pertanyaan. Saya tidak mengetahui algoritma deterministik yang lebih baik daripada untuk min cut (lihat Stoer-Wagner untuk algoritma mudah yang mencapai waktu berjalan ini). Sangat menarik betapa jauh lebih baik kita dapat melakukan deterministik untuk masalah yang Anda tentukan (8/3 dalam eksponen tampaknya tidak wajar untuk ikatan terbaik, tetapi siapa yang tahu). O(mn+n2logn)
Sasho Nikolov

Jawaban:

12

n/2n/2n/2XX¯x:=|X|n/2Xx1Xn/2(x1)x(n/2x+1)x(n/2x+1)n/2, which is true since (x1)(n/2x)0.

Strangely enough, the only reference I find to this result is this from a bioinformatics conference. I'd be really curious to see whether it has been proven somewhere else.

Edit: An earlier reference is: Gary Chartrand: A Graph-Theoretic Approach to a Communications Problem, SIAM J. Appl. Math. 14-4 (1966), pp. 778-781.

Falk Hüffner
sumber