Complexidade Parametrizada de Cliques e Conjuntos Independentes em Grafos Prismas Complementares
Resumo
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.
Referências
Bondy, J. A. and Murty, U. S. R. (1976). Graph theory with applications, volume 290. Macmilan.
Cygan, M., Fomin, F. V., Kowalik, Ł., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., and Saurabh, S. (2015). Parameterized algorithms, volume 3. Springer.
dos Santos, V. F. and dos Santos Souza, U. (2015). Uma introdução à complexidade parametrizada.
Duarte, M. A., Penso, L., Rautenbach, D., and dos Santos Souza, U. (2017). Complexity properties of complementary prisms. Journal of Combinatorial Optimization, 33(2):365–372.
Erdös, P. and Szekeres, G. (1935). A combinatorial problem in geometry. Compositio Mathematica, 2:463–470.
Haynes, T. W., Henning, M. A., Slater, P. J., and van der Merwe, L. C. (2007). The complementary product of two graphs. Bulletin of the Institute of Combinatorics and its Applications, 51:21–30.
Cygan, M., Fomin, F. V., Kowalik, Ł., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., and Saurabh, S. (2015). Parameterized algorithms, volume 3. Springer.
dos Santos, V. F. and dos Santos Souza, U. (2015). Uma introdução à complexidade parametrizada.
Duarte, M. A., Penso, L., Rautenbach, D., and dos Santos Souza, U. (2017). Complexity properties of complementary prisms. Journal of Combinatorial Optimization, 33(2):365–372.
Erdös, P. and Szekeres, G. (1935). A combinatorial problem in geometry. Compositio Mathematica, 2:463–470.
Haynes, T. W., Henning, M. A., Slater, P. J., and van der Merwe, L. C. (2007). The complementary product of two graphs. Bulletin of the Institute of Combinatorics and its Applications, 51:21–30.
Publicado
26/07/2018
Como Citar
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
.
p. 125-128.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2018.3166.
