Complexidade Parametrizada de Cliques e Conjuntos Independentes em Grafos Prismas Complementares - Camargo, Priscila; Carneiro, Alan D. A.; Santos, Uéverton S. (Anais do Encontro de Teoria da Computação (ETC), 2018)
Um grafo do tipo prisma complementar GG̅ surge da união disjunta do grafo G e do seu complementar G̅ e a adição de um emparelhamento perfeito entre os vértices correspondentes em G e G̅. Os problemas clássicos determinar se no grafo existe uma clique de ordem k e determinar se no grafo existe um conjunto independente de ordem k são 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. Nós provamos que estes problemas possuem um núcleo e, portanto são Tratáveis por Parâmetro Fixo (FPT). Em seguida, mostramos que ambos não admitem núcleo polinomial.