Siklus terpanjang terkandung dalam dua siklus

Apakah masalah berikut NP-complete? (Saya anggap ya).

Input: grafik tidak terarah di mana set edge dapat didekomposisi menjadi dua siklus sederhana disjointing edge (ini bukan bagian dari input). $k \in \mathbb{N},G=(V,E)$

Pertanyaan: Apakah ada siklus sederhana dalam dengan panjang lebih besar dari ? $G$ $k$

Jelas masalahnya adalah dalam NP dan derajat maksimum dalam adalah , tetapi itu tampaknya tidak membantu. $G$ $\leq 4$

graph-theory np-complete decision-problem Daftar
sumber

Saya tidak berpikir Anda benar tentang "paling banyak 4 jalur yang menghubungkan setiap pasangan". Lihat: i.imgur.com/mYL4n1V.png

svinja

@svinja Anda benar, saya seharusnya mengatakan paling banyak 4 jalur disjoint edge berpasangan ada di antara setiap pasangan dari dua simpul.

Listing

Judul Anda menyesatkan, karena siklus sederhana terpanjang bisa tidak satu pun dari dua siklus dalam dekomposisi

(dalam dekomposisi apa pun).

E

$E$

Denis

@ Gelas itu sebenarnya bisa, lihat penyatuan dua titik sederhana siklus disjoint.

Listing

Maksud saya bukanlah bahwa itu tidak mungkin menjadi salah satu dari mereka, itu adalah bahwa kadang-kadang itu bukan salah satu dari mereka. Jadi masalahnya bukan menemukan yang lebih besar dari keduanya.

Denis

Jawaban:

Upaya pengurangan ....

Pengurangan dari jalur Hamilton pada digraf dengan derajat 3 maksimal yaitu NPC [G&J] $G = (V,E)$

abaikan arah tepi, dan menggunakan pemindaian kedalaman pertama (tidak terarah) dari simpul arbitrer, bagilah tepi dalam dua set jalur yang berbeda (tidak diarahkan) (merah dan hijau pada gambar); $G$
bergabung dengan jalur merah menambahkan "menghubungkan node" tambahan (simpul ungu pada gambar B) dan membuat sirkuit merah tidak diarahkan; bergabung dengan jalur hijau menambahkan "menghubungkan node" tambahan (simpul ungu pada gambar) dan membuat sirkuit hijau tidak diarahkan;
mentransformasikan setiap simpul asli dari indegree 1 dan outdegree 2 (gambar C), menambahkan yellow node pada edge merah inbound , dan menambahkan yellow node pada edge merah outbound pertama ; akhirnya tambahkan titik kuning "ke arah" tepi hijau keluar kedua menggunakan jalur "terbungkus" di sekitar yang menyentuh titik kuning paling luar dari tepi merah (gambar D). $b \in V$ $k$ $a\to b$ $k$ $b \to c$ $k$ $b \to d$ $b$

Dalam grafik yang dihasilkan, semua simpul kuning dapat dilalui oleh jalur sederhana hanya dalam dua cara yang ditunjukkan pada gambar E dan gambar F, yang sesuai dengan dua traversal yang valid dari simpul asli ; informal jika tepi menuju "ungu" simpul ungu tambahan digunakan, kuning tidak dapat dilalui. $3k$ $b \in V$ $k$

mentransformasikan setiap simpul asli V dari indegree 2 dan outdegree 1 dengan cara yang serupa

Memilih cukup besar , grafik hasil memiliki panjang jalur sederhana lebih besar dari jika dan hanya jika grafik asli memiliki jalur Hamiltonian (panjang ) $k \gg |V|$ $G'$ $3k(|V|-1)$ $G$ $|V|-1$

masukkan deskripsi gambar di sini

Gambar yang lebih besar dapat diunduh di sini

Vor
sumber

Ini adalah bukti yang sangat indah, mungkin Anda harus mengarahkan tepian pada gambar 'A' untuk membuatnya lebih mudah untuk memahami cara mendapatkan jalan (saya pikir saya memahaminya).

Listing

@Listing: konstruksi jalan tidak tergantung pada tepi yang diarahkan (memang saya menulis pencarian "tidak terarah" dalam jawabannya). Anda harus mulai dari node arbitrer, melakukan pemindaian mendalam pertama dari itu mewarnai dengan merah tepi dilalui, kemudian mundur ke derajat 3 node pertama ditemui dan melanjutkan pemindaian kedalaman pertama dari itu mewarnai dengan hijau tepi dilintasi, dan sebagainya. .. mungkin itu memiliki definisi yang lebih formal, tetapi itu tidak muncul di benak saya sekarang. Beri tahu saya jika Anda membutuhkan detail lebih lanjut.

Vor

Saya melihat, properti yang ujung-ujungnya dilintasi pada arah yang 'benar' ditegakkan oleh transformasi terakhir. Terimakasih atas klarifikasinya.

Listing

Terinspirasi oleh jawaban Vor, saya ingin memberikan yang lebih sederhana.

Mulai dengan masalah siklus Hamiltonian untuk masalah grafik grid yang terbukti sulit oleh Itai.

Dapat dengan mudah dilihat bahwa set tepi grafik grid dapat dipartisi menjadi 2 himpunan bagian yang terpisah: horisontal dan vertikal.

Jadi sekarang, kita perlu menenun semua yang horizontal menjadi satu siklus sederhana, dan menenun semua yang vertikal menjadi siklus sederhana lainnya.

Ini adalah tugas yang sangat mudah: untuk yang vertikal, sapu dari paling kiri ke kanan, cukup sambungkan celah vertikal apa pun, lalu sambungkan garis vertikal terkoordinasi x berturut-turut, lalu sambungkan simpul paling kiri ke bawah dengan simpul paling kanan paling atas. Lakukan hal yang sama untuk tepi horizontal.

Perhatikan bahwa grafik yang diperoleh masih sederhana, tidak diarahkan, dan memenuhi persyaratan. Ini sederhana karena pada langkah terakhir fase vertikal dan fase horizontal, kita berurusan dengan dua pasangan simpul yang berbeda.

$k$ $k$ $2k|V|$

Thinh D. Nguyen
sumber