Complexidade Parametrizada de Cliques e Conjuntos Independentes em Grafos Prismas Complementares

  • Priscila Camargo
  • Alan D. A. Carneiro
  • Uéverton S. Santos

Resumo


The complementary prism GG¯ arises from the disjoint union of the graph G and its complement G¯ by adding the edges of a perfect matching joining pairs of corresponding vertices of G and G¯. The classical problems of graph theory, clique and independent set were proved NP-complete when the input graph is a complemantary prism. In this work, we study the complexity of both problems in complementary prisms graphs from the parameterized complexity point of view. First, we prove that these problems have a kernel and therefore are Fixed-Parameter Tractable (FPT). Then, we show that both problems do not admit polynomial kernel.

Publicado
26/07/2018
CAMARGO, Priscila; CARNEIRO, Alan D. A.; SANTOS, Uéverton S.. Complexidade Parametrizada de Cliques e Conjuntos Independentes em Grafos Prismas Complementares. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 3. , 2018, Natal. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2018 . ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2018.3166.