O isomorfismo do subgráfico induzido é fácil em uma subclasse infinita?

Existe uma sequência de gráficos não direcionados , em que cada tem exatamente vértices e o problema $\{C_n\}_{n\in \mathbb N}$ $C_n$ $n$

Dados e um gráfico , é um subgrafo induzido de ? $n$ $G$ $C_n$ $G$

é conhecido por estar na classe ? (Por exemplo, quando , esse é o problema de clique NP-complete.) $\mathsf{P}$ $C_n=K_n$

cc.complexity-theory graph-theory sdcvvc
fonte

Crosspost de cs.stackexchange.com/questions/10576 #

sdcvvc

Então faz parte da definição do problema, faz parte da entrada e faz parte da entrada?

{C_{n}}

$\{ C_n \}$

n

$n$

G

$G$

Andrew D. Rei

@ Andrew D. King: Sim.

Sdcvvc

E se for uma estrela (um nó central conectado a nós que formam um conjunto independente)? para verificar, apenas enumere todos os nós do grau em e verifique se os vizinhos formam um conjunto independente.

C_{n}

$C_n$

n - 1

$n-1$

n - 1

$n-1$

G

$G$

Suresh Venkat

@ Suresh: Pode haver um vértice de grau maior que , cujos vizinhos formam um conjunto independente. Encontrá-los é NP-completo.

n - 1

$n-1$

n - 1

$n-1$

sdcvvc

Respostas:

Se não me engano, sua pergunta foi respondida pelo módulo de Chen-Thurley-Weyer-2008 parametrizado pressupostos de complexidade.

Ainda não li o artigo com cuidado, mas, tanto quanto entendi, há uma dicotomia no sentido de que se é finito, o problema está em , mas se possui um número infinito de gráficos, o isomorfismo do subgrafo induzido está completo (Corolário 4, página 6). $C$ $P$ $C$ $W[1]$

Assim, parece que a menos que o primeiro nível da hierarquia colapsa para , não há uma classe de tais infinito de gráficos cujos induzida subgráfico isomorfismo é em . $W[1]$ $W$ $FPT$ $P$

Há outro resultado interessante afirmando que, se , existem classes para as quais o isomorfismo induzido não está nem em nem em completo. $P\neq NP$ $P$ $NP$

Mateus de Oliveira Oliveira
fonte