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

Abstract

A connection tree of a graph G for a non-empty subset W ⊆ V (G) is a tree subgraph of G such that W ⊆ V (T) and every leaf of T belongs to W. The vertices in W are called terminals, the vertices in V (T) \ W with degree 2 in T are called linkers and the vertices in V (T) \ W with degree at least 3 in T are called routers. In 2012, Dourado et al. proposed the Terminal connection problem (TCP), which consists in the following question: “given a connected graph G, a terminal set W and two non-negative integers ` and r; does G admit a connection tree for W such that it has at most ` linkers and at most r routers? ”. The TCP was proved to be NP-complete even when either ` or r is bounded by a constant; conversely, the problem was proved to be polynomial-time solvable if ` and r are both bounded by constants. Later, in 2014, Dourado et al. proposed the strict variant of the TCP which further requires that every terminal must be a leaf of T, and it is denoted by S-TCP. As the TCP, the S-TCP was proved to be NP-complete if ` is bounded by a constant and be polynomial-time solvable if ` and r are both bounded by constants; however, the case in which just r is bounded by a constant was not considered. Thus, we study in this dissertation the S-TCP restricted to the case in which r is bounded by a constant. More specifically, we provide a polynomial-time algorithm for the S-TCP when r ∈ {0, 1} and we prove partial results for the case r ≥ 2, exposing relations with network flows and disjoint paths. Moreover, we determine the complexity of some variants of the S-TCP. Lastly, we study the S-TCP and the TCP when the maximum degree of the graph G is bounded.