Penyelesaian siklus ganjil minimum chordless minimum: apakah ini NP-hard?

Masalah menarik berikut muncul dalam penelitian saya baru-baru ini:

INSTAN: Grafik . $G(V, E)$

SOLUSI: Selesai siklus aneh chordless, didefinisikan sebagai superset dari edge set sehingga grafik memiliki properti yang setiap tepi dalam terkandung dalam siklus aneh chordless. $E'$ $E$ $G'(V, E')$ $G'$

UKURAN: Ukuran penyelesaian, yaitu,. $|E' - E|$

Sejauh ini, kami dapat membuktikan bahwa versi modifikasi dari masalah ini adalah NP-complete, di mana alih-alih mengharuskan "setiap tepi dalam terkandung dalam siklus ganjil yang tanpa kabel" kami membutuhkan properti yang lebih kuat bahwa "setiap tepi terkandung dalam sebuah segitiga (siklus panjang 3) ". (Perhatikan bahwa ini tidak setara dengan masalah MINIMUM CHORDAL GRAPH COMPLETION .) $G'$

Yang pertama dengan mudah dilihat sebagai generalisasi dari yang terakhir, tetapi sejauh ini semua upaya saya untuk membuktikannya gagal. Adakah yang bisa datang dengan pointer / referensi / dll?

cc.complexity-theory reference-request graph-theory np-hardness Gabor Retvari
sumber

masalah tampaknya sangat terkait dengan grafik sempurna yang sempurna jika ada lubang aneh (anti-) (siklus aneh chordless setidaknya panjang 5) [lebih lanjut di wikipedia]. Karena itu sarankan mungkin Anda mencoba untuk memformat ulang pertanyaan dalam hal pertanyaan pada grafik yang sempurna.

vzn

@ vz: Saya tidak yakin teorema yang kuat ini bisa membantu di sini.

domotorp

Bisakah kita memutuskan dalam P apakah setiap tepi G terkandung dalam siklus aneh chordless? Saya kira ini mungkin, tetapi saya tidak tahu caranya.

domotorp

Kami punya dua masalah sekarang. Mudah, kita akan memiliki keputusan dalam P jika kita dapat memutuskan untuk setiap sisi apakah itu dalam siklus ganjil chordless. Saya menemukan referensi , menyatakan bahwa pertanyaan "Apakah grafik mengandung siklus aneh yang panjangnya lebih besar dari tiga, melewati titik yang ditentukan?" dan "Apakah grafik berisi jalur ganjil yang diinduksi antara dua simpul yang ditentukan?" NP-complete, tetapi ini tidak menyelesaikan kasus kami sepenuhnya. Mungkin ternyata masalah aslinya bukan pada NP, tetapi masih bisa NP-hard.

Gabor Retvari

dapatkah Anda menunjukkan bagian dari makalah Anda menentukan masalah di atas & apa yang ada dalam makalah yang Anda maksudkan spec. to ("versi modifikasi selesai NP lengkap")

vzn

Kami membuktikan bahwa masalahnya adalah NP-hard bahkan dalam bentuk keputusannya, yaitu '' Apakah grafik input sudah merupakan penyelesaian siklus aneh yang tidak berantai? '' Dengan mengurangi dari masalah berikut: $G$

Masalah P : Diberikan grafik dan tepi , apakah ada siklus aneh panjang yang lebih besar dari 3 melewati ? $G$ $e\in E(G)$ $e$

Masalah ini dikenal sebagai NP-keras dengan pengurangan dari '' mendeteksi siklus genap chordless yang melewati node tertentu '' dalam referensi yang diberikan dalam salah satu komentar Anda yang dinyatakan dalam paragraf sebelum bagian 3 dengan membiarkan dan : $p=0$ $q=2$

Sebagai tambahan, misalkan dan menjadi bilangan bulat tetap yang berubah-ubah. Masalah-masalah berikut ini adalah NP-complete: Apakah grafik mengandung siklus yang diinduksi melalui simpul ditentukan , dengan panjang (mod )? ... $q>1$ $p\ge 0$ $G$ $u$ $p$ $q$

(Mungkin ada pengurangan Karp, tetapi jika kita mengizinkan satu Cook, pertimbangkan pengurangan berikut: Mengganti derajat d simpul yang diberikan ke subgraph lengkap ukuran d dengan tepi keluar yang tepat. Kemudian untuk setiap tepi dalam grafik lengkap kita bisa query oracle yang memecahkan Masalah P. Perhatikan bahwa siklus genap tanpa chord yang melewati node yang diberikan sesuai dengan siklus ganjil chordless dengan panjang lebih besar dari 3 melewati salah satu ujung dalam grafik lengkap.)

Sekarang untuk reduksi utama. Diberikan contoh Masalah P, pertama kami mendeteksi jika ada segitiga yang melewati ; jika demikian, hapus setiap node yang membentuk segitiga dengan . Perhatikan bahwa menghapus node yang membentuk segitiga dengan tidak akan menghapus siklus aneh chordless yang melewati (oleh properti chordless). $e$ $e$ $e$ $e$

Selanjutnya, untuk setiap sisi selain dari kami menambahkan simpul bantu dan dua sisi dan . Perhatikan bahwa grafik baru memiliki properti berikut: $f$ $e=(u,v)$ $v_f$ $(v_f,u)$ $(v_f,v)$ $G'$

memiliki siklus aneh chordless dengan panjang lebih dari 3 melewati jika dan hanya jika adalah penyelesaian chordless aneh-siklus. $G$ $e$ $G'$

Untuk satu-satunya arah, dapat dibuktikan dengan mempertimbangkan berbagai jenis tepi dalam . Setiap sisi selain dari (termasuk tepi yang baru ditambahkan) akan memiliki setidaknya satu segitiga (yang berisi simpul bantu); dan akan berada dalam siklus ganjil chordless di karena ada siklus ganjil chordless melewati di , dan siklus tidak dihapus selama proses penghapusan simpul. $G'$ $e$ $e$ $G′$ $e$ $G$

Untuk arah if, karena setiap tepi selain harus dalam setidaknya satu segitiga, kita hanya perlu khawatir tentang tepi . Ada siklus aneh chordless melewati dalam ( adalah penyelesaian siklus aneh chordless). Siklus tidak dapat memiliki panjang 3 dengan konstruksi , dan karena siklus tidak dapat mengandung node bantu (oleh properti tanpa kabel), ia akan berada dalam grafik juga. Karena itu buktinya lengkap. $e$ $e$ $e$ $G'$ $G'$ $G'$ $G$

Hsien-Chih Chang 張顯之
sumber

Saya mengalami kesulitan mengikuti salah satu dari pengurangan tersebut. Dalam reduksi pertama, jika simpul v yang diberikan memiliki derajat, katakanlah, 5, maka setelah reduksi itu menjadi K_5, dan K_5 ini mengandung siklus panjang ganjil, tetapi tidak sesuai dengan siklus panjang-rata yang berisi v. reduksi utama, misalkan G = (V, E) di mana V = {1,2,3,4,5}, E = {12,23,34,45,15,35}, dan e = 34. G memiliki siklus dengan panjang 5 yang melewati e, tetapi dalam G ', edge 34 adalah jembatan dan tidak termasuk dalam siklus aneh, jika saya memahami definisi pengurangan Anda dengan benar.

Tsuyoshi Ito

e

$e$

e

$e$

e

$e$

G^{'}

$G'$

@ Hsien-ChihChang 張顯之: Ngomong-ngomong: karena hadiahnya segera berakhir dan saya akan berada jauh dari komputer saya, saya menghadiahkan Anda dengan harganya sekarang. Terima kasih banyak atas jawaban Anda, itu benar-benar membantu saya memikirkan masalah dengan cara baru. Jika Anda bisa kembali lagi nanti dan membereskan masalah di atas, saya akan sangat berterima kasih.

Gabor Retvari

e

$e$

e

$e$

G^{'}

$G'$

G^{'}

$G'$

e

$e$

e

$e$

G^{'}

$G'$

e

$e$

G

$G$

Hsien-Chih Chang 張顯之

Penyelesaian siklus ganjil minimum chordless minimum: apakah ini NP-hard?

Jawaban: