Bagaimana cara menghasilkan grafik acak yang tidak memiliki siklus Hamilton?

Biarkan kelas A menunjukkan semua grafik ukuran yang memiliki siklus Hamilton. Sangat mudah untuk menghasilkan grafik acak dari kelas ini - ambil node terisolasi, tambahkan siklus Hamiltonian acak dan kemudian tambahkan tepi secara acak. $n$ $n$

Biarkan kelas B menunjukkan semua grafik ukuran yang tidak memiliki siklus Hamilton. Bagaimana kita bisa memilih grafik acak dari kelas ini? (atau melakukan sesuatu yang dekat dengan itu) $n$

ds.algorithms graph-theory Jagadish
sumber

Bagaimana jelas bahwa prosedur pertama menghasilkan grafik secara acak secara acak? Sudah jelas bahwa itu selalu menghasilkan grafik Hamilton, tetapi karena Anda menambahkan tepi secara acak nanti, Anda mungkin memperkenalkan lebih banyak siklus Hamilton, membuat beberapa grafik lebih sering muncul daripada yang lain.

Robin Kothari

Ini benar tetapi distribusi seragam tidak diminta (jika mungkin tersirat).

Raphael

Ya, saya tidak peduli tentang keseragaman. Saya ingin memberi setiap grafik di keluarga grafik non-Hamilton beberapa peluang untuk dipilih. Masalah dengan pengambilan sampel yang seragam cukup mendasar: AFAIK, kita tidak tahu bagaimana sampel secara seragam dari keluarga ukuran grafik n, apalagi yang dengan siklus Hamiltonian.

Jagadish

Jawaban:

Ini tidak mungkin (kecuali NP = coNP) karena khususnya yang menyiratkan fungsi poli-waktu yang rentangnya adalah grafik non-Hamiltonian (fungsi beralih dari string acak ke grafik output), yang pada gilirannya akan menyiratkan NP-proof non-Hamiltonianicity (untuk membuktikan G tidak memiliki sirkuit Hamilton, tunjukkan x yang memetakannya.)

Noam
sumber

Anda berasumsi bahwa fungsi seperti itu ada di-ke kelas grafik non-Hamilton. Ini hanya terjadi jika kita ingin distribusinya seragam. Lihat juga komentar Aaron di bawah ini: cstheory.stackexchange.com/questions/562/…

Ohad Kammar

Ini tidak mengasumsikan apa-apa tentang probabilitas memilih setiap grafik (seperti itu seragam), hanya bahwa grafik yang mungkin dihasilkan oleh algoritma adalah persis non-Hamiltonian (ke). Jika Anda mengizinkan kesalahan di kedua sisi, maka memang ini mungkin terjadi.

Noam

Saya setuju, bukan keseragaman distribusi yang penting, melainkan fakta bahwa semua grafik non-Hamilton memiliki probabilitas yang tidak nol. Jika salah satu dari mereka memiliki probabilitas nol, bukti Anda tidak berlaku (tanpa pengetahuan lebih lanjut tentang dukungan distribusi).

Ohad Kammar

@Ohad: jika salah satu dari mereka tidak terjawab, maka Anda bisa menambahkan ini ke tabel pencarian. Saya pikir masalahnya hanya dimulai jika Anda kehilangan sebagian positif dari mereka, tetapi kemudian Anda tidak mengambil sampel secara seragam.

Emil

Jika algoritma Anda menghasilkan distribusi yang seragam pada grafik non-Hamiltonian dengan probabilitas dan grafik Hamiltonian dengan probabilitas , dan saat ukuran input masuk ke , maka saya pikir Anda harus dapat untuk menggabungkan algoritme ini dengan fungsi hash acak untuk menemukan bukti interaktif putaran konstan dari non-Hamiltonicity. Ini akan menyiratkan bahwa hierarki polinomial runtuh

1 - ϵ

$1-\epsilon$

ϵ

$\epsilon$

ϵ \to 0

$\epsilon \rightarrow 0$

\infty

$\infty$

Peter Shor

Bollobas, Fenner, dan Frieze (http://portal.acm.org/citation.cfm?id=22145.22193) memberikan algoritma waktu polinomial untuk menemukan siklus Hamiltonian dalam grafik acak, yang memiliki tingkat kesalahan yang cenderung asimtotik cenderung 0 dalam ukuran. dari grafik. Jika Anda ingin membuat grafik n vertex yang bukan Hamiltonian, Anda dapat memilih grafik acak dengan $G_{n,m}$ $m$ sedemikian rupa sehingga grafik adalah Hamiltonian dengan probabilitas konstan yang dibatasi dari 1. Anda kemudian dapat menjalankan algoritma BFF untuk mencoba menemukan siklus Hamiltonian di dalamnya, dan menolak grafik jika algoritma berhasil. Setelah jumlah putaran yang konstan, Anda akan mengharapkan untuk menemukan grafik yang algoritmenya gagal menemukan siklus Hamilton, dan meskipun grafik ini mungkin sebenarnya adalah Hamiltonian, kemungkinan hal ini akan berkurang dalam . $n$

Tentu saja, ini tidak memilih seragam secara acak dari himpunan semua grafik verteks non-Hamiltonian , tetapi ia memilih dari subkelas yang menarik - yang mana Anda akan mengharapkan sebagian kecil dari grafik menjadi Hamilton, serta fraksi nontrivial tidak. $n$

Aaron Roth
sumber

Ini adalah ide yang baik, meskipun kita dapat melewatkan seluruh algoritma probabilistik untuk menemukan siklus Ham. Pertanyaannya tidak menanyakan bahwa prosedur pengambilan sampel berjalan dalam waktu yang diharapkan atau apa pun. Jadi buat grafik acak dari distribusi favorit Anda, tentukan apakah itu Hamiltonian dengan beberapa algoritma yang tepat, dan jika itu Hamiltonian maka buang dan ulangi prosesnya. Jika distribusi yang digunakan adalah distribusi seragam pada semua grafik berlabel, ini sebenarnya akan menghasilkan setiap grafik berlabel non-Hamilton dengan probabilitas seragam.

JimN

Tugas pertama mudah karena grafik Hamilton mudah diverifikasi. Namun, Tidak ada bukti singkat yang diketahui yang dapat diverifikasi secara efisien untuk menyaksikan bahwa grafik yang diberikan adalah non-Hamilton.

Mohammad Al-Turkistany
sumber

Saya pikir jawaban Turki memunculkan pertanyaan yang menarik. Secara umum apakah mungkin untuk mengambil sampel secara seragam dari bahasa yang dilengkapi dengan NP bersama?

Suresh Venkat

.... dan Noam menjawab itu secara negatif.

Suresh Venkat