Multicortes em Árvores de Grau Limitado

Cristina Gomes Fernandes (Georgia Tech e USP)

O Problema dos Multicortes é o seguinte: dado um grafo G e uma coleção de pares de vértices distintos s_{i}, t_{i} de G, encontrar um conjunto mínimo de arestas de G cuja remoção desconecta cada s_{i} do t_{i} correspondente. Sabese que esse problema é NP-difícil mesmo quando restringimos o grafo de entrada a ser uma árvore. Provamos que, para árvores binárias, o problema continua NP-difícil. Para árvores em geral, a melhor razão de aproximação conhecida é dois. Nós apresentamos, para todo ϵ > 0, um algoritmo de aproximação polinomial com razão no máximo 1 + ϵ para árvores de grau limitado. Para o caso particular de árvores binárias, o algoritmo pode ser implementado em tempo linear.

Esse trabalho é conjunto com Gruia Călinescu do Georgia Institute of Technology - EUA.