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

18

Existe uma sequência de gráficos não direcionados , em que cada tem exatamente vértices e o problema{Cn}nNCnn

Dados e um gráfico , é um subgrafo induzido de ?nGCnG

é conhecido por estar na classe ? (Por exemplo, quando , esse é o problema de clique NP-complete.)PCn=Kn

sdcvvc
fonte
1
Então faz parte da definição do problema, faz parte da entrada e faz parte da entrada? {Cn}nG
Andrew D. Rei
1
@ 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. Cnn1n1G
Suresh Venkat
4
@ Suresh: Pode haver um vértice de grau maior que , cujos vizinhos formam um conjunto independente. Encontrá-los é NP-completo. n1n1
sdcvvc

Respostas:

15

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).CPCW[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]WFPTP

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

Mateus de Oliveira Oliveira
fonte