Connection of terminals with router limitations: complexity and relationship with flows and disjoint paths

• 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

Abstract

We investigate the complexity of the TERMINAL CONNECTION PROBLEM (TCP), a network design problem closely related to several classical problems. Particularly, we analyse the strict version of TCP, denoted by S-TCP, when the parameter r is bounded by a constant. We prove that, for r ∈ {0, 1}, S-TCP is polynomial-time solvable, contrasting with the complexity of TCP, which is known to be NP-complete for all r ≥ 0. Furthermore, in order to better understand the cases in which r ≥ 2, we study some variants of the S-TCP and relate it to network flow and disjoint path problems. We prove the NP-completeness of an integral network flow problem, closing a forty-year complexity gap. Finally, we establish a poly vs. NP-c dichotomy for TCP and S-TCP regarding the maximum degree of the input graph and the parameter.

References

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.