CLIQUES E CONJUNTOS INDEPENDENTES EM GRAFOS PRISMAS COMPLEMENTARES: COMPLEXIDADE E TRATABILIDADE PARAMETRIZADA

Um grafo do tipo prisma complementar surge da união disjunta do grafo G e do seu
complementar G
e a adição de um emparelhamento entre os vértices correspondentes em G e G
Dois
problemas clássicos da teoria dos grafos, determinar se no grafo existe uma clique de ordem k e
determinar se no grafo existe um conjunto independente de ordem k foram provados NP-completos
quando o grafo de entrada é um prisma complementar. Neste trabalho, estudamos a complexidade
de ambos os problemas em grafos prismas complementares sob a ótica da complexidade parametrizada.
Inicialmente provamos utilizando que estes problemas possuem um
núcleo e, portanto são Tratáveis por Parâmetro Fixo (FPT). Em seguida, mostramos através de PPT
reduções que tanto determinar se o grafo possui uma clique quanto determinar se o grafo possui um
conjunto independente em grafos prisma complementares quando parametrizados pelo tamanho da
solução k não possuem núcleo polinomial.