Cristina Gomes Fernandes (cris@ime.usp.br)
6a. feira - 13 de março - 14 horas
Sala 259-A
Resumo: O problema dos Multicortes pode ser definido da seguinte forma: dado um grafo $G$ e uma coleção de pares $s_i, t_i$ de vértices distintos de $G$, encontrar um conjunto mínimo de arestas de $G$ cuja remoção desconecta cada $s_i$ do $t_i$ correspondente. Sabe-se que o problema dos Multicortes é NP-difícil e Max SNP-difícil mesmo quando a entrada é restrita a ser uma árvore. Para árvores em geral, o problema dos Multicortes é pelo menos tão difícil quanto o problema de Cobertura de Vértices e a melhor razão de aproximação conhecida é dois. No semestre passado, apresentamos em um dos nossos seminários um esquema de aproximação polinomial (PTAS) para Multicortes em árvores de grau limitado e mostramos que Multicortes em árvores binárias ainda é NP-difícil. Nesse seminário, apresentaremos um PTAS para o problema dos Multicortes em grafos de grau e largura arbórea limitados. Além disso, mostraremos que o problema é NP-difícil em paredes (walls), uma classe de grafos contendo grafos com largura arbórea tão grande quanto quisermos.
Esse trabalho foi feito em conjunto com Bruce Reed.