Seminário de Combinatória do IME-UFF

Data: 30/06/2021 (quarta-feira)

Horário: 14h

Sala: https://meet.google.com/npz-qztp-riw

Palestrante: Vinícius Fernandes dos Santos, Universidade Federal de Minas Gerais.

Título: Reducing graph transversals via edge contractions

Resumo:

For a graph parameter $\pi$, the Contraction($\pi$) problem consists in, given a graph G and two positive integers k,d, deciding whether one can contract at most k edges of G to obtain a graph in which $\pi$ has dropped by at least d. Galby et al. [ISAAC 2019, MFCS 2019] recently studied the case where $\pi$ is the size of a minimum dominating set. We focus on graph parameters defined as the minimum size of a vertex set that hits all the occurrences of graphs in a collection H according to a fixed containment relation. We prove co-NP-hardness results under some assumptions on the graphs in H, which in particular imply that Contraction($\pi$) is co-NP-hard even for fixed k=d=1 when $\pi$ is the size of a minimum feedback vertex set or an odd cycle transversal. In sharp contrast, we show that when $\pi$ is the size of a minimum vertex cover, the problem is in XP parameterized by d.

Joint work with Paloma T. Lima, Ignasi Sau and Uéverton S. Souza, available at arXiv:2005.01460.

O Seminário de Combinatória continua as suas atividades de forma online, apoiando as medidas de distanciamento social determinadas durante a pandemia do COVID-19. Desta vez agradecemos a presença do professor Vinícius dos Santos do DCC-UFMG.

Emitiremos certificados de participação para Atividade Complementar. Basta colocar seu nome completo, instituição de origem, e e-mail no Chat ao final do seminário.

Não é necessária inscrição prévia. 

Nossos seminários acontecem regularmente desde 2015 e todas as ações podem ser encontradas em:

http://www.antenabrasil.uff.br/index.php/pt-br/acoes/seminario-combinatoria

Agradecemos a presença e a ajuda na divulgação. Compartilhem!