Partisi grafik menjadi siklus simpul-terpisah

Masalah terkait: Teorema Veblen menyatakan bahwa "Sebuah grafik mengakui dekomposisi siklus jika dan hanya jika itu genap". Siklusnya adalah edge disjoint, tetapi tidak harus simpul disjoint. Dengan kata lain, "Kumpulan tepi grafik dapat dipartisi menjadi siklus jika dan hanya jika setiap titik memiliki derajat genap."

Masalah saya: Saya bertanya-tanya apakah ada yang mempelajari partisi grafik ke dalam siklus simpul-terpisah. Yaitu, partisi simpul dari grafik G menjadi V 1 , V 2 , ⋯ , V k , dan setiap subgraf yang diinduksi oleh V i adalah Hamilton.$V$$G$$V_1, V_2, \cdots, V_k$$V_i$

Apakah NP-keras atau mudah?

Masalah yang lebih terkait: Partisi ke dalam segitiga adalah NP-complete. (Halaman 68 dari "Komputer dan sifat tidak praktis")

Terima kasih atas saran Anda sebelumnya. ^^

Partisi ke dalam siklus vertex-disjoint adalah hal yang sama dengan subgraph 2-reguler, lebih dikenal sebagai 2-faktor. Itu dapat ditemukan (jika ada) dalam waktu polinomial oleh suatu algoritma berdasarkan pencocokan. Misalnya lihat tautan ini .

ETA Nov 2013: Tampaknya dari komentar di bawah ini bahwa pengurangan dari sumber yang ditautkan di atas salah. Namun, pernyataan bahwa masalah dapat dikurangi menjadi pencocokan sempurna tetap benar. Pengurangan yang benar adalah dalam WT Tutte (1954), "Sebuah bukti singkat dari teorema faktor untuk grafik berhingga", Canadian J. Math. 6: 347–352 .

Ganti setiap simpul dengan derajat d dengan grafik bipartit lengkap G v = K d $v$$d$ , dan mewakili setiap tepiuvdari grafik asli dengan tepi dari satu titik dari G u ke salah satu simpul dari G v (di sisi bipartisi dengandsimpul) sedemikian rupa bahwa setiap simpul dari G v di sisi bipartisi itu persis memiliki satu insiden tepi seperti itu.$G_v=K_{d,\,d-2}$$uv$$G_u$$G_v$$d$$G_v$

Kemudian matching sempurna dalam grafik dimodifikasi harus sesuai dengan simpul di pihak mereka dari bipartisi dari G v dengan d - 2 keluar dari d simpul di sisi lain, meninggalkan tepat dua simpul gratis yang perlu dicocokkan dengan tetangga mereka di subgraphs lainnya G u . Dengan cara ini, pencocokan sempurna dari grafik yang dimodifikasi sesuai 1-untuk-1 dengan penutup siklus dari grafik asli.$d-2$$G_v$$d-2$$d$$G_u$