Temukan siklus negatif dengan kendala titik

Diberi grafik dengan tepian berbobot, bagaimana kita bisa menemukan siklus negatif yang mengandung setidaknya satu simpul dalam set simpul yang diberikan ? Terima kasih.$\{V_1, V_2, \ldots, V_k\}$

Jika Anda tidak memerlukan siklus sederhana, maka pecahkan grafik (terarah) menjadi komponen-komponen yang terhubung kuat, dan untuk setiap komponen yang mengandung salah satu dari simpul yang diberikan , periksa apakah komponen tersebut mengandung siklus negatif. Jika tidak ada komponen yang berfungsi, tidak ada siklus negatif yang mengandung V i . Tetapi jika beberapa komponen melakukannya, Anda dapat menemukan siklus negatif (non-sederhana) yang mengandung V i dengan mengambil banyak salinan dari siklus negatif, dan menambahkan ke jalur itu ke dan dari beberapa titik dalam siklus ke V i . (Total waktu untuk menemukan representasi implisit dari siklus yang diinginkan akan sama dengan waktu untuk menemukan siklus negatif dalam grafik yang diarahkan, misalnya O $V_i$$V_i$$V_i$$V_i$ , jika saya ingat.)$O(nm)$

Jika Anda memerlukan siklus untuk menjadi sederhana, maka masalahnya menjadi NP-lengkap, bahkan jika hanya satu simpul diberikan. (Anda dapat mengurangi Hamiltonian Path ke masalah: untuk menemukan jalur Hamiltonian dari sumber S yang diberikan ke wastafel T dalam grafik G yang diberikan , berikan bobot tepi yang ada -1, lalu tambahkan simpul buatan V 1 dengan dua tepi dari biaya N / 2 - 0,01 masing-masing, satu dari V 1 ke S dan satu dari T ke V 1. )$V_1$$S$$T$$G$$V_1$$N/2-0.01$$V_1$$S$$T$$V_1$

Jika Anda membiarkan siklus untuk mengulang simpul tetapi tidak tepi, saya percaya itu masih NP-lengkap (dengan pengurangan yang sama, tetapi membelah setiap simpul menjadi tepi yang diarahkan ( v , v ′ ) dengan cara standar).$v$$(v,v')$

Saya akan menganggap input Anda adalah grafik terarah; Saya tidak tahu bagaimana melakukan ini untuk kasus yang tidak diarahkan.

Buat salinan set simpul dari grafik Anda, di mana n adalah jumlah simpul dalam grafik. Ganti setiap tepi dari u ke v dalam grafik asli Anda dengan tepi yang pergi dari copy i dari u untuk menyalin i + 1 dari v , untuk semua pilihan saya . Selain itu, jika Anda milik set simpul yang ditentukan tetapi tidak sebaliknya, sertakan juga tepi dari copy i of u ke copy 0 of v .$n$$n$$u$$v$$i$$u$$i+1$$v$$i$$u$$i$$u$$0$$v$

Siklus dalam grafik yang diperluas semua proyek kembali ke siklus dalam grafik asli, tetapi setiap siklus dalam grafik yang diperluas berisi salah satu simpul yang ditentukan (jika tidak, Anda tidak dapat mundur melalui lapisan ekspansi), sehingga grafik asli berisi siklus negatif yang berisi simpul yang ditentukan jika grafik diperluas berisi siklus negatif.