Apakah isomorfisma subgraph yang diinduksi mudah pada subclass yang tak terbatas?

Apakah ada urutan grafik diarahkan , di mana masing-masing memiliki tepat simpul dan masalah $\{C_n\}_{n\in \mathbb N}$ $C_n$ $n$

Mengingat dan grafik , adalah merupakan subgraf diinduksi ? $n$ $G$ $C_n$ $G$

dikenal di kelas ? (Misalnya, ketika , ini adalah masalah klik NP-lengkap.) $\mathsf{P}$ $C_n=K_n$

cc.complexity-theory graph-theory sdcvvc
sumber

Crosspost

sdcvvc

Jadi

adalah bagian dari definisi masalah,

adalah bagian dari input, dan

adalah bagian dari input?

{C_{n}}

$\{ C_n \}$

n

$n$

G

$G$

Andrew D. King

@Andrew D. King: Ya.

sdcvvc

Bagaimana jika

adalah bintang (satu simpul pusat yang terhubung ke

simpul yang membentuk set independen)? untuk memeriksa, cukup sebutkan semua simpul derajat

dalam

, dan periksa apakah tetangga membentuk perangkat independen.

C_{n}

$C_n$

n - 1

$n-1$

n - 1

$n-1$

G

$G$

Suresh Venkat

@Suresh: Mungkin ada titik berderajat lebih besar dari

, yang beberapa

tetangga membentuk set independen. Menemukan mereka adalah NP-lengkap.

n - 1

$n-1$

n - 1

$n-1$

sdcvvc

Jawaban:

Jika saya tidak salah, pertanyaan Anda dijawab oleh Chen-Thurley-Weyer-2008 modulo asumsi kompleksitas parameter.

Saya belum membaca makalah dengan seksama, tetapi sejauh yang saya mengerti, ada dikotomi dalam arti bahwa jika terbatas maka masalahnya ada di , tetapi jika memiliki jumlah grafik yang tak terbatas maka isomorfisma subgraf yang diinduksi adalah lengkap (Akibat 4, halaman 6). $C$ $P$ $C$ $W[1]$

Dengan demikian tampaknya bahwa kecuali tingkat pertama dari hirarki runtuh ke , tidak ada kelas yang tak terbatas seperti grafik yang diinduksi subgraph isomorfisma dalam . $W[1]$ $W$ $FPT$ $P$

Ada hasil menarik lainnya yang menyatakan bahwa jika maka ada kelas yang isomorfisma yang diinduksi tidak dalam atau lengkap. $P\neq NP$ $P$ $NP$

Mateus de Oliveira Oliveira
sumber