Alur maksimum menggunakan Ford-Fulkerson dan DFS

22

Pertanyaan ini adalah tentang kompleksitas waktu dari algoritma aliran maksimum Ford-Fulkerson ketika menggunakan DFS untuk menemukan jalur tambahan.

Ada contoh terkenal yang menunjukkan bahwa menggunakan DFS seseorang dapat memerlukan jumlah iterasi linier dalam aliran maksimum, lihat misalnya halaman Wikipedia yang ditautkan di atas.

Namun, saya tidak benar-benar yakin dengan contoh ini: implementasi DFS standar tidak akan menunjukkan perilaku bolak-balik antara B dan C sebagai simpul pertama jalur (menggunakan nama vertex dari halaman Wikipedia).

Jadi, mari kita terapkan kondisi yang sangat alami bahwa setiap kali DFS mengunjungi simpul , selalu memeriksa tetangga Anda dalam urutan yang sama. Apakah masih ada contoh dimana FF dengan DFS menggunakan sejumlah besar iterasi?uu

Sebagai varian, anggaplah bahwa kita memiliki properti tambahan yang urutan tetangganya berbeda konsisten dengan beberapa pemesanan global yang tetap namun tetap dari simpul tersebut. Apakah itu membuat perbedaan?

Bagi saya, ini sepertinya pertanyaan mendasar; Saya minta maaf sebelumnya jika jawabannya sudah diketahui tetapi saya bukan pakar arus dan beberapa Google tidak menemukan apa pun.

Sunting: Jawabannya ternyata ya, masih ada contoh. Lihat Gambar 2 dari makalah ini . Dalam contoh-contoh ini FF dengan DFS mengambil jumlah iterasi (dalam jumlah simpul) yang berulang. Tampaknya mudah untuk membuktikan bahwa ini ketat, yaitu, bahwa jumlah iterasi selalu dibatasi oleh (terlepas dari nilai kapasitas).2O(n)

ds.algorithms reference-request max-flow Per Austrin
sumber
4
Saya bertanya-tanya tentang pertanyaan yang sama.
Luca Trevisan
1
(1) Pertanyaan yang bagus. (2) Saya pikir contoh buruk (seperti yang ada di Wikipedia) biasanya diperkenalkan sebagai alasan mengapa beberapa pertimbangan tentang pesanan kunjungan diperlukan, bukan sebagai alasan untuk tidak menggunakan pencarian kedalaman-pertama.
Tsuyoshi Ito
6
Saya tidak berpikir saya sekarang bisa mengajar FF tanpa jawaban untuk pertanyaan ini. Bagus !!
Suresh Venkat
Tidak menemukan aliran maksimum dalam iterasi minimal NP-Complete?
user834

Jawaban:

13

Jika daftar adjacency diperbaiki terlebih dahulu maka DFS selalu berakhir (bahkan jika ada kapasitas irasional).

Lihat Dean, Goemans, Immorlica - Finite Termination dari "Augmenting Path" Algoritma dalam Kehadiran Data Masalah Irasional .

ilyaraz
sumber
11
Terima kasih. Itu tidak dengan sendirinya menjawab pertanyaan saya, namun, contoh yang diberikan pada Gambar 2 dari makalah Dean-Goemans-Immorlica menunjukkan konstruksi rekursif berdasarkan contoh standar, yang menjawab pertanyaan saya dan menunjukkan bahwa FF dengan DFS dapat membutuhkan banyak secara eksponensial banyak iterasi.
Per Austrin