Conexão de terminais com limitação de roteadores: complexidade e relação com fluxos e caminhos disjuntos
Resumo
Investigamos a complexidade do PROBLEMA DE CONEXÃO DE TERMINAIS (TCP), um problema de projeto de redes diretamente relacionado a diversos problemas clássicos. Particularmente, analisamos a versão estrita do TCP, denotada por S-TCP, quando o parâmetro r é limitado por uma constante. Provamos que, para r 2 f0; 1g, o S-TCP é solucionável em tempo polinomial, o que contrasta com a complexidade do TCP, que é sabidamente NP-completo para todo r 0. Ademais, com o intuito de compreender melhor os casos em que r 2, estudamos algumas variantes do S-TCP e o relacionamos com problemas de fluxo em redes e de caminhos disjuntos. Provamos a NP-completude de um problema de fluxo integral, fechando uma questão em aberto por quarenta anos. Por fim, estabelecemos uma dicotomia poly vs. NP-c para o TCP e para o S-TCP com respeito ao grau máximo do grafo entrada e ao parâmetro.
