Saya ingin Gadget mudah untuk membuktikan Planar Hamiltonian Cycle NP-Complete (dari Hamiltonian Cycle)

Diketahui bahwa Siklus Hamiltonian (disingkat Ham) adalah NP-complete dan Planar Ham Cycle adalah NP-Complete. Buktinya untuk Planar Ham Cycle bukan dari Ham Cycle.

Apakah ada gadget bagus yang akan, diberi grafik G, mengganti semua penyeberangan dengan beberapa gadget planar sehingga Anda memiliki grafik planar G 'sedemikian rupa sehingga

G memiliki siklus Ham jika G 'memiliki siklus Ham.

(Saya akan senang dengan varian - seperti Ham path atau Ham Cycle yang diarahkan atau Directed Ham Path.)

cc.complexity-theory np-hardness planar-graphs hamiltonian-paths Bill GASARCH
sumber

Pengamatan yang agak sepele. Misalkan Anda menyematkan

dan ujung

dan

silang, dengan

muncul searah jarum jam di sekitar titik persimpangan. Ganti dengan gadget

yang memiliki empat titik masuk

sesuai dengan

G

$G$

(x, y)

$(x,y)$

(u, v)

$(u,v)$

x, v, y, u

$x,v,y,u$

P_{x v y u}

$P_{xvyu}$

x^{'}, v^{'}, y^{'}, u^{'}

$x',v',y',u'$

. Jika siklus hamiltonian dalam

menggunakan kedua sisi

x, v, y, u

$x,v,y,u$

G

$G$

(x, y)

$(x,y)$ dan

maka dalam

siklus yang sesuai harus self-lintas. Hal ini tentu saja mengasumsikan penafsiran naif sebagian besar dari apa yang `` gadget" adalah dan juga bahwa siklus Hamiltonian dalam

kebutuhan untuk mengikuti tepi yang sama seperti yang sesuai siklus dalam

(u, v)

$(u,v)$

G^{'}

$G'$

G^{'}

$G'$

G

$G$

Marek Chrobak

Apa itu Ham Cycle? Tolong jangan menganggap semua orang mengerti singkatan Anda.

Tsuyoshi Ito

@MarekChrobak: Saya setuju dengan komentar Anda. Anda memberi dua cara untuk menghindari pertengkaran Anda. Saya pikir yang paling alami adalah yang kedua: Ada Siklus Hamiltonian

dalam

jika ada Siklus Hamiltonian

x \to y \to \dots \to u \to v \to \dots \to x

$x\to y\to\dotsb\to u\to v\to\dotsb\to x$

G

$G$

x \to x^{'} \to \dots \to u^{'} \to u \to \dots \to y \to y^{'} \to \dots \to v^{'} \to v \to \dots \to x

$x\to x'\to\dotsb \to u'\to u\to\dotsb\to y\to y'\to\dotsb\to v'\to v\to\dotsb\to x$

Bruno

@ Tsuyoshi: Itu berarti siklus Hamilton. Saya pikir masuk akal untuk mengasumsikan bahwa semua orang bisa mengetahuinya.

domotorp

@ Bill: Saya bertanya-tanya mengapa menurut Anda gadget seperti itu ada. Jumlah penyeberangan saat menyematkan grafik sembarang ke dalam bidang bisa sangat besar (

untuk grafik lengkap - lihat lemma penyeberangan). Jadi, jika Anda mulai dengan grafik dengan

tepi dan banyak sisi (katakanlah dekat kuadrat) maka grafik yang disematkan dengan penyilangan ditambahkan sebagai simpul memiliki struktur yang sama sekali berbeda ...

Θ (n^{4})

$\Theta(n^4)$

n

$n$

Sariel Har-Peled

Jawaban:

Setidaknya, tidak ada gadget "bagus" untuk satu crossover.

Biarkan dan menjadi tanda silang yang ingin kita ganti. $(a, b)$ $(x,y)$ masukkan deskripsi gambar di sini

Ada banyak kasus untuk grafik kami, , tetapi kami harus memenuhi setidaknya empat berikut. Kasus 1: setidaknya ada satu siklus hamiltonian, tetapi tidak ada yang menggunakan salah satu ujungnya. Kasus 2: setidaknya ada satu siklus, dan semua siklus menggunakan persis salah satu dari dua sisi. Kasus 3: setidaknya ada satu siklus, dan semua siklus menggunakan kedua sisi. Kasus 4: tidak ada siklus hamiltonian. $G$

Jika gadget kami memiliki dua (atau lebih) simpul untuk masing-masing $a, b, x, y$ $a_0$ $a_1$ $a$ $G'$

$(a, x), (y, b)$ $(a, y), (x, b)$ $(a, y), (y, b), (x,b)$

$G'$ $G$ $G = (V, E)$ $V = \{a, b, x, y, p, q, r, s, t\},$ $E = \{(a, b), (x, y), (a, r), (a, p), (a, q), (b, s), (b, x), (p, s), (p, t), (p, y), (q, x), (r, y), (t, x)\}$ $G$ masukkan deskripsi gambar di sini

$G' = (V, E')$ $E' = \{(a, y), (y, b), (x, b)\} \cup$ $\{(x, y), (a, r), (a, p), (a, q), (b, s), (p, s), (p, t), (p, y), (q, x), (r, y), (t, x)\}$ $G'$ $a, q, x, t, p, s, b, y, r, a$

$(b, y)$ $(a, x)$ $G'$

$(a, b), (a, y), (x, b)$

Karena menambahkan tiga edge break case 4, menambahkan lebih banyak tidak akan membantu.

$a, b, x$ $y$

(Catatan: beri tahu saya jika saya membuat kesalahan di atas!)

( ~~Catatan 2: Saya memiliki beberapa angka yang bagus, tetapi tidak dapat mempostingnya.~~ Diposting.)

Kyle
sumber

Saya pikir Anda harus dapat memposting angka sekarang.

Jukka Suomela