Apakah ada algoritma yang efisien untuk masalah tutupan simpul ini?

Saya telah berusaha menemukan algoritma untuk menemukan penutup siklus simpul maksimum dari grafik - yaitu, serangkaian siklus terpisah yang berisi semua simpul dalam G , dengan sebanyak mungkin siklus (kami tidak mempertimbangkan siklus individu di sini). Saya tahu bahwa masalah menemukan penutup siklus simpul minimum , serta menemukan penutup siklus simpul dengan siklus k persis adalah NP-lengkap. Tapi bagaimana dengan case maksimal?$G$$G$$k$

Sementara saya akan menemukan jawaban yang menarik ini secara umum, grafik yang saya ingin gunakan untuk ini sebenarnya cukup dibatasi oleh konstruksi mereka, jadi mungkin bahkan jika masalahnya NP-lengkap mungkin ada solusi polinomial untuk contoh-contoh khusus ini.

Kami memiliki daftar bilangan bulat , elemen l i dan kami akan menggunakan S , elemen s i untuk merujuk ke L setelah mengurutkannya. Sebagai contoh:$L$$l_i$$S$$s_i$$L$

Verteks grafik akan diidentifikasi dengan pasangan sedemikian rupa sehingga l i = n dan s i ≠ n . Grafik memiliki tepi terarah ( n , i ) → ( m , j ) jika dan hanya jika s j = n . (Siklus dalam grafik ini sesuai dengan serangkaian nilai yang dapat diijinkan secara siklikal sehingga akan berakhir pada posisi yang diurutkan.)$(n, i)$$l_i = n$$s_i \neq n$$(n, i) \rightarrow (m, j)$$s_j = n$

Contoh di atas akan menghasilkan grafik berikut (menggunakan indeks berbasis 1):

Satu hal yang tidak berhasil adalah pendekatan rakus dengan berulang kali menghapus siklus terkecil (seperti yang ditunjukkan contoh ini).

Perhatikan bahwa masalah ini (jika saya tidak membuat kesalahan) setara dengan menanyakan berapa swap yang Anda perlukan untuk mengurutkan daftar yang diberikan . (Itulah yang mengilhami mencari masalah ini sejak awal.)

Setelah beberapa petunjuk dari jawaban Juho dan sedikit lebih memilah-milah literatur, saya telah menemukan masalah penugasan yang tampaknya terkait sangat erat. Namun, masalah penugasan dirumuskan dalam bentuk grafik bipartit tertimbang dan sejauh ini saya belum dapat menemukan cara untuk memilih tepi dan bobot untuk mengurangi masalah ini. Jika kita ingin merumuskan masalah di sini dalam hal meminimalkan fungsi bobot, maka pendekatan intuitif akan mengatakan bahwa bobot setiap siklus adalah dimana | C | adalah jumlah tepi (atau simpul) dalam siklus. (Tentu saja ini setara dengan hanya mengatur bobot ke - $|C|-1$$|C|$$-1$.) Artinya, berat tergantung pada ukuran siklus, bukan tepi tertentu yang tercakup. Tapi mungkin ini memberi seseorang ide lain untuk mengurangi masalah.

Tampaknya juga membatasi ukuran siklus membuat masalah APX-sulit untuk grafik umum. Ini tidak selalu menyiratkan bahwa hal yang sama berlaku untuk tugas memaksimalkan jumlah siklus, atau untuk grafik tertentu yang sedang dipertimbangkan di sini, tetapi tampaknya cukup erat terkait bahwa itu bisa menjadi penting.

Singkatnya: Dapatkah penutup siklus titik puncak maksimum ditemukan untuk grafik yang dibuat dari proses di atas?

Sebagai dua sisi, saya juga akan tertarik pada apakah penutup siklus vertex disjoint maksimum juga memiliki solusi yang efisien untuk grafik arbitrer yang menerima setidaknya satu siklus penutup (yang mungkin akan jatuh sebagai jawaban untuk pertanyaan utama), atau apakah hanya dengan menentukan jumlah siklus dalam penutup maksimum (yang bertentangan dengan tepi aktual yang terkandung di masing-masing) membuat masalah lebih mudah. Saya senang memposting ini sebagai pertanyaan terpisah jika orang berpikir mereka layak mendapatkan jawaban penuh sendiri.

$G$$k$$k=2$$k=3$ $k$$k$

$G$$G$$((3/5)-\epsilon)$$\epsilon > 0$

Untuk detail dan bukti klaim di atas, lihat [1].

[1] Bläser, Markus, dan Bodo Manthey. "Dua algoritma perkiraan untuk penutup 3-siklus." Algoritma Perkiraan untuk Optimalisasi Kombinatorial. Springer Berlin Heidelberg, 2002. 40-50.