Cara menghasilkan grafik dengan tutup vertex optimal yang diketahui

Saya sedang mencari cara untuk menghasilkan grafik sehingga penutup vertex optimal diketahui. Tidak ada batasan pada jumlah node atau tepi, hanya bahwa grafik sepenuhnya terhubung.

idenya adalah untuk menghasilkan grafik yang tidak mudah untuk menemukan penutup simpul optimal, untuk dapat menguji heuristik yang berbeda di atasnya

Saya menemukan makalah Arthur, J. & Frendeway, J. Menghasilkan Masalah Travelling-Salesman dengan Tur Optimal yang Diketahui, Jurnal Masyarakat Riset Operasional, Vol. 39, No. 2 (Feb., 1988), hlm. 153-159 untuk menghasilkan TSP yang dikenal optimal, sayangnya saya tidak dapat mengaksesnya.

Apakah ada algoritma yang dikenal?

ds.algorithms graph-theory graph-algorithms AndresQ
sumber

"Tidak ada batasan pada jumlah node atau tepi, hanya bahwa grafik sepenuhnya terhubung." Anda perlu batasan lebih dari ini. Kalau tidak, saya menghasilkan set grafik lengkap dan tahu penutup vertex optimal untuk masing-masing.

Tyson Williams

M

$M$

e \in M

$e \in M$

C

$C$

C

$C$

C

$C$

K_{3}

$K_3$

Saya kira "menghasilkan grafik bipartit acak dan menghitung penutup verteksnya" tidak dihitung sebagai jawaban yang berguna ...

David Eppstein

ada banyak strategi untuk membuat instance SAT "hard" & juga repositori instance "hard" yang diarsipkan jika Anda bersedia menempuh rute itu - yaitu mengonversi instance SAT ke vertex cover. juga ada banyak penelitian yang mempelajari SAT dari pov empiris yang secara alami diterjemahkan menjadi semua masalah NP lengkap lainnya misalnya titik transisi dll. banyak referensi tentang semua ini ...

vzn

Bahkan lebih umum daripada solvabilitas waktu polinomial penutup Vertex pada grafik Koning seperti dicatat oleh David, hasil berikut diketahui dari bidang kompleksitas parameter: ada c konstan sehingga untuk setiap integer tetap k, ada O (n ^ c) algoritma waktu untuk menguji apakah grafik memiliki penutup simpul yang melebihi ukuran maksimum pencocokannya paling banyak k. Grafik Konig adalah kasus khusus ketika k = 0.

Bart Jansen

Jawaban:

Memperluas komentar vzn menjadi jawaban: Pengurangan standar dari CNF-SAT ke penutup titik cukup mudah: buat titik untuk setiap istilah (variabel atau negasi), hubungkan setiap variabel ke negasinya dengan tepi, buat klik untuk setiap klausa , dan hubungkan setiap simpul dalam klik ke simpul untuk salah satu istilah dalam klausa. Jika Anda mulai dengan masalah kepuasan dengan penugasan memuaskan yang diketahui, ini akan memberi Anda masalah penutup simpul dengan solusi optimal yang diketahui (pilih simpul istilah yang diberikan oleh penugasan, dan di setiap klausa klik pilih semua kecuali satu simpul, sehingga klausa titik yang tidak dipilih berbatasan dengan istilah titik yang dipilih).

Jadi sekarang Anda perlu menemukan masalah kepuasan yang memiliki tugas memuaskan yang diketahui tetapi di mana solusinya sulit ditemukan. Ada banyak cara yang diketahui untuk menghasilkan masalah kepuasan yang sulit (misalnya menghasilkan contoh k-SAT acak dekat dengan ambang kepuasan) tetapi persyaratan tambahan yang Anda tahu tugas yang memuaskan membatasi kemungkinan. Satu hal yang dapat Anda lakukan di sini adalah melalui tingkat reduksi lain, dari masalah yang sulit secara kriptografis seperti faktorisasi. Yaitu memilih dua bilangan prima besar p dan q, mengatur sirkuit Boolean untuk mengalikan p dan q sebagai angka biner, dan menerjemahkannya ke dalam rumus CNF di mana ada variabel untuk setiap input (p dan q) dan untuk setiap nilai menengah pada kawat di sirkuit, klausa untuk setiap output memaksanya memiliki nilai yang tepat, dan klausa untuk setiap gerbang yang memaksa input dan output gerbang agar konsisten satu sama lain. Kemudian terjemahkan rumus CNF ini ke dalam simpul penutup.

Untuk strategi yang lebih sederhana, pilih tugas yang memuaskan ke rumus 3CNF terlebih dahulu, dan kemudian buat klausa secara acak, pertahankan hanya klausa yang konsisten dengan tugas, dan kemudian konversikan ke penutup simpul. Jika klausa memiliki probabilitas seragam, ini akan rentan terhadap heuristik berbasis gelar (istilah simpul yang cocok dengan tugas yang dipilih akan memiliki derajat lebih rendah daripada istilah simpul yang tidak) tetapi kekurangan ini dapat dihindari dengan menyesuaikan probabilitas klausa sesuai dengan berapa banyak ketentuan klausul yang setuju dengan penugasan yang dipilih. Mungkin ini rentan terhadap beberapa jenis serangan waktu polinomial tetapi mungkin bukan yang wajar untuk penutup verteks, sehingga mungkin membuat serangkaian contoh uji yang baik meskipun tidak memiliki banyak jaminan kekerasan.

David Eppstein
sumber

\cap

$\cap$

referensi terdekat yang saya temukan adalah - Pada contoh sulit perkiraan titik dekat oleh Sundar Vishwanathan. tidak melihat referensi untuk melihat contoh sulit dari masalah yang tepat.

seperti dalam komentar saya, ada banyak penelitian dalam pendekatan yang sesuai untuk SAT yang dapat direduksi menjadi penutup verteks.

Kembali komentar, ide untuk membuat instance acak dan hanya memilih contoh yang sulit untuk algoritma standar tampaknya benar-benar masuk akal bagi saya khususnya dengan pendekatan penelitian empiris / eksperimental [1], ini merupakan prosedur operasi standar untuk penelitian serupa ke dalam SAT titik transisi. [2]

yang omong-omong memang memiliki sesuatu untuk dikatakan di mana wilayah "keras" adalah untuk masalah NP lengkap lainnya [3,4,5] yang berhubungan secara kasar dengan titik kritis dalam "kepadatan" 1s dalam contoh acak yang ditentukan dalam biner. untuk penutup simpul ini mungkin berhubungan dengan kerapatan tepi.

Perhatikan bahwa membuktikan seseorang dapat membangun satu set contoh keras, dan hanya contoh keras, pada dasarnya setara dengan masalah P vs NP. analisis yang lebih formal tentang kesetaraan ini ada dalam makalah Razborov / Rudich Natural Proofs.

[1] algoritme eksperimental

[2] Penelitian transisi fase SAT

[3] Transisi Fase dalam Masalah Keras NP

[4] Transisi fase dalam masalah NP-lengkap: tantangan untuk probabilitas, kombinatorik, dan ilmu komputer oleh Moore

[5] Fase transisi perilaku oleh Walsh

vzn
sumber