Conexão de terminais com limitação de roteadores: complexidade e relação com fluxos e caminhos disjuntos

• Alexsander Andrade de Melo UFRJ
• Celina Miraglia Herrera de Figueiredo UFRJ
• Uéverton dos Santos Souza UFF

DOI: https://doi.org/10.5753/ctd.2018.3651

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 ∈ {0, 1}, 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.

Referências

Dourado, M. C., Oliveira, R. A., Protti, F., and Souza, U. S. (2014a). Design of connection networks with bounded number of non-terminal vertices. In proceedings of V Latin-American Workshop on Cliques in Graphs, LAWCG 2012, volume 42 of Matemática Contemporânea, pages 39–47. SBM.

Dourado, M. C., Oliveira, R. A., Protti, F., and Souza, U. S. (2014b). Conexão de terminais com número restrito de roteadores e elos. In annals of XLVI Simpósio brasileiro de pesquisa operacional, pages 2965–2976.

Even, S., Itai, A., and Shamir, A. (1976). On the complexity of timetable and multicommodity flow problems. SIAM Journal on Computing, 5(4):691–703.

Karp, R. M. (1975). On the computational complexity of combinatorial problems. Networks, 5:45–68.

Melo, A. A., de Figueiredo, C. M. H., and Souza, U. S. The strict terminal connection problem with a bounded number of routers. In proceedings of VII Latin-American Workshop on Cliques in Graphs, LAWCG 2016, Matemática Contemporânea (to appear).

Melo, A. A., de Figueiredo, C. M. H., and Souza, U. S. (2017). Simple undirected two-commodity integral flow with a unitary demand. In proceedings of Latin and American Algorithms, Graphs and Optimization Symposium, LAGOS 2017, volume 62 of Eletronic Notes in Discrete Mathematics, pages 279–284.

Robertson, N. and Seymour, P. D. (1995). Graph minors. xiii. the disjoint paths problem. Journal of Combinatorial Theory, Series B, 63(1):65–110.