Partisi bebas-H

Ini adalah pertanyaan yang terinspirasi oleh masalah pemotongan bebas-H . Diberikan grafik, partisi dari simpulnya mengatur menjadi bagian adalah -gratis jika tidak menginduksi salinan untuk semua , . $V$ $r$ $V_1, V_2, \ldots, V_r$ $H$ $G[V_i]$ $H$ $i$ $1 \leq i \leq r$

Saya ingin mempertimbangkan pertanyaan berikut:

Apa yang paling tidak memiliki partisi bebas- menjadi bagian ? $r$ $H$ $r$

Perhatikan bahwa ketika adalah satu sisi, maka ini sama dengan menemukan angka kromatik, dan sudah selesai NP. Saya bertanya-tanya apakah lebih mudah untuk menunjukkan NP-kelengkapan untuk setiap tetap untuk masalah ini (lebih mudah, dibandingkan dengan menunjukkannya untuk free cut). Saya bahkan berpikir itu mungkin sudah jelas, tetapi saya tidak mendapatkan apa-apa. Sangat mungkin saya melewatkan sesuatu yang sangat mudah, dan jika ini masalahnya, saya akan menghargai beberapa petunjuk! $H$ $H$ $H$

graph-theory np-hardness co.combinatorics Neeldhara
sumber

Maksud Anda: untuk semua

dan untuk semua

, subgraf

diinduksi oleh

bukan isomorfik terhadap

i

$i$

U \subseteq V_{i}

$U \subseteq V_i$

G

$G$

U

$U$

H

$H$

Jukka Suomela

Saya pikir jawaban RJK untuk masalah lain terkait dari ini berlaku untuk masalah ini (sebenarnya lebih baik daripada masalah lainnya).

Tsuyoshi Ito

@ Jukka: Cukup, saya tahu. Terima kasih atas penunjuknya, dan maafkan saya karena terlalu malas (setidaknya untuk sekarang) untuk memperbarui pertanyaan yang sesuai!

Neeldhara

@ Tsuyoshi: Ya, dan sekarang saya memiliki versi jawaban yang lebih rumit di sini juga! Namun, saya harus mengatakan bahwa saya memposting ini karena saya menemukan diri saya dalam situasi "Saya-memukul-hambatan-sambil-memikirkan-tentang-X dan Y-tampaknya-yang-terkait-dan-lebih mudah memulai". Saya hanya berpikir saya harus membagikan perincian Y untuk yang lain yang memikirkan X, dan itu terutama tidak dimaksudkan sebagai permintaan referensi :)

Neeldhara

Serge Gaspers merujuk pada sebuah makalah Lewis dan Yannakakis (1980) yang lama (sepertinya) sangat relevan di sini!

RJK

Jawaban:

Referensi paling awal yang saya tahu untuk jenis masalah ini adalah sebagai berikut. Ini juga disebut dalam kertas Cowen, Goddard dan Jesurum yang saya sebutkan di utas lainnya.

Andrews dan Jacobson. (1985) Tentang generalisasi bilangan kromatis. Dalam Proc. Konferensi Internasional Tenggara ke-16 tentang Combinatorics, Teori Grafik dan Komputasi (Boca Raton 1985), Congr. Angka 47 33–48.

Cowen, Cowen dan Woodall. (1986) Pewarnaan yang cacat pada grafik di permukaan: Partisi menjadi subgraph dari valensi terikat. J. Grafik Theory 10 187–195.

Harary. (1985) Colorability bersyarat dalam grafik. Dalam Grafik dan Aplikasi (Boulder 1982), Wiley – Interscience, hlm. 127–136.

Harary, dan Jones (nee Fraughnaugh). (1985) Colorability bersyarat II: Variasi bipartit. Dalam Proc. Konferensi Sundance tentang Combinatorics dan Topik Terkait (Sundance 1985), Congr. Angka 50 205–218.

AFAIK, belum ada makalah yang memberikan dikotomi P / NP-c eksplisit untuk berbagai pilihan H. Namun, ini telah dilakukan oleh Hell dan Nesetril, untuk jenis generalisasi lain dari nomor kromatik, "pewarnaan-H ", untuk homomorfisme.

RJK
sumber

Terima kasih banyak atas jawaban Anda yang sangat terperinci - sangat dihargai. Itu tambahan yang substansial ke daftar bacaan saya, itu harus membuat saya sibuk untuk sementara waktu!

Neeldhara

Yah, tidak masalah, meskipun, seperti yang saya sebutkan sebelumnya, selain kertas JGT, cukup sulit untuk melacaknya. (Sebenarnya, saya harus mengakui bahwa saya belum banyak berhasil, walaupun telah memiliki akses ke banyak perpustakaan universitas Kanada.) Bagaimanapun, makalah Cowen, Goddard dan Jesurum mungkin paling relevan dan menjawab pertanyaan Anda / Moron untuk H menjadi bintang tetap, bahkan terbatas pada grafik planar. Mungkin kelas H terbaik terbuka (saya pikir?) Untuk menenggelamkan gigi adalah siklus atau klik.

RJK

$F_1$ $F_2$ $F_1$ $F_2$ $F_1$ $F_2$

(Bebas F = {untuk semua H dalam F, Bebas H}}

Lihat www.combinatorics.org/Volume_11/PDF/v11i1r46.pdf

Aravind
sumber