Data: 06/05/2021, às 16:00 horas (GMT-3, horário de Brasília).
Título: Algoritmos parametrizados para conjuntos dominantes localizadores
Palestrante: Márcia Cappelle (UFG)


Resumo: Um conjunto dominante localizador D de um grafo G é um conjunto dominante de G onde cada vértice que não está em D tem uma vizinhança única em D. O problema CONJUNTO DOMINANTE LOCALIZADOR pergunta se G tem um tal conjunto de tamanho limitado. Este problema é NP-difícil mesmo em classes de grafos restritas, como grafos de intervalo, split, e grafos bipartidos planares subcúbicos. Por outro lado, ele pode ser resolvido em tempo polinomial para árvores e, de forma mais geral, para grafos com cliquewidth limitada. Consideramos a kernelização do problema sob aspectos estruturais de parametrização. Apresentamos um kernel exponencial parametrizado por distância para cluster e mostramos que, a menos que NP seja um subconjunto de co-NP/Poly, nenhum kernel polinomial existe para CONJUNTO DOMINANTE LOCALIZADOR, quando parametrizado ou por cobertura de vértices ou por distância para clique. Além disso, consideramos um parâmetro não limitado pelos dois anteriores e exibimos um kernel polinomial quando parametrizado pelo número max-folha.

Trabalho realizado em conjunto com Guilherme Gomes e Vinicius dos Santos.