Grafik kubik sisi-partisi menjadi cakar dan jalur

Lagi-lagi masalah pembagian-tepi yang kerumitannya membuat saya penasaran, termotivasi oleh pertanyaan saya sebelumnya .

Input: grafik kubik $G=(V,E)$

Pertanyaan: apakah ada partisi ke E 1 , E 2 , ... , E s , sehingga subgraph disebabkan oleh masing-masing E i adalah salah cakar (yaitu K 1 , 3 , sering disebut bintang) atau 3 -path (yaitu P 4 )?$E$$E_1, E_2, \ldots, E_s$$E_i$$K_{1,3}$$3$$P_4$

Saya pikir saya melihat makalah suatu hari di mana masalah ini terbukti sebagai NP-lengkap, tetapi saya tidak dapat menemukannya lagi, dan saya tidak ingat apakah hasil itu diterapkan pada grafik kubik. Pada masalah terkait, saya sadar bahwa mempartisi-tepi grafik bipartit ke dalam cakar adalah NP-complete (lihat Dyer dan Frieze ). Apakah ada yang punya referensi untuk masalah yang saya jelaskan, atau sesuatu yang terkait (yaitu masalah yang sama pada kelas grafik lain, yang kemudian bisa saya coba kurangi menjadi grafik kubik)?

Ini bukan jawaban untuk kompleksitas masalah, tetapi setidaknya menunjukkan bahwa kompleksitas memiliki peluang menjadi nontrivial: ini adalah contoh grafik kubik yang tidak dapat dipartisi menjadi jalur dan cakar.

_{(sumber: uci.edu )}

Dalam masing-masing dari tiga lobusnya, setiap partisi menjadi jalur dan cakar hanya dapat menggunakan enam dari tujuh tepi. Enam tepi tengah yang tersisa berbentuk cakar dengan masing-masing ujungnya dibagi, yang tidak dapat dipartisi menjadi lintasan dan cakar.

ETA : Grafik yang ditunjukkan di atas lebih terkenal sebagai contoh grafik kubik tanpa pencocokan sempurna. Tetapi setiap grafik kubik dengan pencocokan sempurna memiliki dekomposisi ke jalur (bahkan tidak menggunakan cakar apa pun). Menurut teorema König, ini mencakup semua grafik bipartit kubik dan teorema Petersen, ini mencakup semua grafik kubik tanpa jembatan, menjawab pertanyaan Joseph Malkevitch dalam komentar.

Buktinya sangat sederhana: jika M adalah pencocokan sempurna dalam grafik kubik, penghapusan M meninggalkan grafik 2-reguler, yaitu penyatuan siklus yang terpisah-pisah. Orientasikan setiap siklus secara sewenang-wenang, dan lampirkan setiap tepi uv M ke tepi siklus yang mengikuti u dan v dalam orientasi siklusnya.

Di arah lain, jika ada dekomposisi ke jalur, maka ada pencocokan sempurna: tepi tengah setiap jalur harus cocok karena tidak ada dua tepi tengah dapat berbagi derajat-tiga titik.

(Penafian: ide ini mungkin telah hadir dalam ceramah yang diundang Carsten Thomassen di GD 2010, yang merupakan masalah penguraian grafik semacam ini.)

(Selain penafian (oleh Anthony Labarre): "ide orientasi" untuk beralih dari pencocokan sempurna ke partisi menjadi jalan muncul dalam makalah ini oleh Jünger, Reinelt dan Pulleyblank , yang menghubungkannya dengan WH Cunningham.)

$k$$k\geq 3$$k=3$$2$$3$

Ini sebenarnya bukan akhir dari cerita: jika grafik kubik adalah bipartit, maka mudah untuk mempartisi tepi yang ditetapkan hanya dengan menggunakan cakar, dengan memilih satu set bipartisi dan menjadikannya satu set "pusat cakar". Masalah umum memang sulit, yang dapat dibuktikan menggunakan pengurangan dari CUBIC PLANAR MONOTONE 1-IN-3 KEPUASAN. Semua detail dapat diakses secara bebas di arxiv .

Mungkin tulisan ini mungkin menarik:

Kleinschmidt, Peter Regular partisi dari grafik reguler. Canad. Matematika Banteng. 21 (1978), no. 2, 177–181.

Ini berkaitan dengan grafik yang dapat ditulis sebagai penyatuan "Z-paths" dengan panjang 3. (Khususnya, planar, 3-valent, 3-terhubung graph-cubic 3-polytopes.)