¿El isomorfismo inducido por subgrafía es fácil en una subclase infinita?

¿Hay una secuencia de gráficos no dirigidos , donde cada tiene exactamente vértices y el problema $\{C_n\}_{n\in \mathbb N}$ $C_n$ $n$

Dado y un gráfico , ¿es un subgrafo inducido de ? $n$ $G$ $C_n$ $G$

se sabe que está en la clase ? (Por ejemplo, cuando , este es el problema de la camarilla completa de NP). $\mathsf{P}$ $C_n=K_n$

cc.complexity-theory graph-theory sdcvvc
fuente

Crosspost

sdcvvc

¿Entonces

es parte de la definición del problema,

es parte de la entrada y

es parte de la entrada?

{C_{n}}

$\{ C_n \}$

n

$n$

G

$G$

Andrew D. King

@ Andrew D. King: Sí.

sdcvvc

¿Qué pasa si

es una estrella (un nodo central conectado a

nodos que forman un conjunto independiente)? para verificar, simplemente enumere todos los nodos de grado

, y verifique si los vecinos forman un conjunto independiente.

C_{n}

$C_n$

n - 1

$n-1$

n - 1

$n-1$

G

$G$

Suresh Venkat

@Suresh: puede haber un vértice de grado mayor que

, cuyos vecinos

forman un conjunto independiente. Encontrarlos es NP-completo.

n - 1

$n-1$

n - 1

$n-1$

sdcvvc

Respuestas:

Si no me equivoco, su pregunta fue respondida por supuestos de complejidad parametrizados del módulo Chen-Thurley-Weyer-2008 .

Todavía no leí el documento con cuidado, pero hasta donde lo entendí, hay una dicotomía en el sentido de que si es finito, entonces el problema está en , pero si tiene un número infinito de gráficos, entonces el isomorfismo inducido del subgrafo está completo (Corolario 4, página 6). $C$ $P$ $C$ $W[1]$

$W[1]$ $W$ $FPT$ $P$

$P\neq NP$ $P$ $NP$

Mateus de Oliveira Oliveira
fuente