Properti grafik NP-complete yang bersifat herediter, tetapi tidak bersifat aditif?

12

Properti grafik disebut herediter jika ditutup sehubungan dengan menghapus simpul (yaitu, semua subgraf yang diinduksi mewarisi properti). Properti grafik disebut aditif jika ditutup sehubungan dengan mengambil serikat terputus-putus.

Tidak sulit untuk menemukan sifat-sifat yang turun temurun, tetapi tidak aditif. Dua contoh sederhana:

$\;\;\;$ (1) Grafik selesai.

$\;\;\;$ (2) Grafik tidak mengandung dua siklus vertex-disjoint.

Dalam kasus ini jelas bahwa properti diwarisi oleh subgraph yang diinduksi, tetapi mengambil dua grafik terpisah yang memiliki properti, serikat mereka mungkin tidak melestarikannya.

Kedua contoh di atas adalah properti decidable polytime (meskipun untuk (2) itu agak kurang sepele). Jika kita menginginkan properti yang lebih keras, mereka masih bisa dibuat dengan mengikuti pola (2), tetapi mengganti siklus dengan tipe grafik yang lebih rumit. Kemudian, bagaimanapun, kita dapat dengan mudah berjalan ke dalam situasi di mana masalahnya bahkan tidak tetap di , di bawah asumsi kompleksitas standar, seperti . Tampaknya kurang sepele untuk menemukan contoh yang tetap dalam , tetapi masih sulit. $NP$ $NP\neq coNP$ $NP$

Pertanyaan: Apakah Anda tahu (sebaiknya alami) properti grafik -Lengkap yang turun-temurun, tetapi tidak aditif? $NP$

cc.complexity-theory graph-theory graph-algorithms np Andras Farago
sumber

4

Anda telah mengajukan sejumlah pertanyaan sekarang tentang properti "alami". Mungkin bermanfaat untuk memahami apa motivasi dari beberapa pertanyaan ini.

Suresh Venkat

1

@ Suresh Saya ingin lebih memahami apa yang membuat masalah alami, sebagai lawan dibuat-buat, buatan. Saya pikir, konsep kealamian adalah jembatan penting antara teori dan kenyataan, dan perlu ditelusuri. Apa yang saya temukan menarik adalah bahwa meskipun kita tidak memiliki definisi formal tentang masalah mana yang "alami," orang biasanya memiliki konsensus yang jelas tentang apakah suatu masalah tertentu adalah alami atau tidak. Mungkin saya akan memposting pertanyaan terpisah tentang masalah ini, untuk mencari tahu lebih lanjut tentang bagaimana orang lain melihatnya.

Andras Farago

9

$k$ $k$

Jelas, mengambil subgraph yang diinduksi tidak dapat membuat ukuran minimum peningkatan partisi tersebut. Di sisi lain, ketika Anda mengambil penyatuan terpisah dari dua grafik, Anda harus mengambil penyatuan partisi menjadi klik masing-masing.

Vinicius dos Santos
sumber

k

$k$

k

$k$

k

$k$

k

$k$

h e r e d i t a r y

$hereditary$

k

$k$

k

$k$

4

k

$k$

k

$k$

1

k = 3

$k=3$

G_{1}

$G_1$

G_{2}

$G_2$

1

Pertimbangkan masalah ini

$G$ $P$ $Q$

Ini tetap NP lengkap bahkan jika sifatnya turun temurun.

Sekarang jelas solusi dari masalah di atas untuk grafik juga menyediakan solusi untuk subgraph yang diinduksi. Tetapi setelah mengambil penyatuan grafik dari keluarga yang sama dengan G mungkin tidak dapat diselesaikan dengan menggunakan solusi itu.

Misalnya mempartisi grafik umum dalam grafik interval satuan disjoint adalah NP lengkap tetapi setelah menggabungkan semua sisi yang memungkinkan (membuat grafik lengkap) menyelesaikan masalah secara sepele.

Dibyayan
sumber

1

Harap perhatikan bahwa pertanyaannya mencari properti yang tidak aditif. Dalam contoh Anda, tampaknya tidak ada yang menjamin bahwa harus ada dua grafik yang keduanya memiliki properti, tetapi penyatuan yang terpisah tidak.

Andras Farago

1

$G = (V,E)$ $C_1,\ldots,C_m$ $C_i$ $V$ $E$ $C_i$

$k \geq 3$ $G$ $k$

$k = 2$

Jika (1) benar maka itu harus menjawab pertanyaan Anda, karena memberikan properti yang turun temurun, tetapi jelas tidak aditif.

(CATATAN TAMBAH: dugaan (2) berbeda dari "dugaan penutup siklus ganda" oleh Szekeres dan Seymour, meskipun homonimitasnya).

Super8
sumber

1

Properti ini bukan keturunan. Penghapusan verteks dapat meningkatkan jumlah siklus yang diperlukan untuk menutupi semua sisi, karena verteks yang dihapus dapat menghilangkan siklus yang digunakan untuk menutupi banyak sisi. Contoh paling sederhana adalah ketika seluruh grafik hanyalah sebuah siklus. Penghapusan vertex membuat setiap siklus tidak memungkinkan, karena tidak ada siklus yang tersisa.

Andras Farago

G

$G$

G

$G$

v

$v$

v

$v$

k

$k$

Properti grafik NP-complete yang bersifat herediter, tetapi tidak bersifat aditif?

Jawaban: