Minimum t-Spanners on Subcubic Graphs

Autor(es)

Gomez, Renzo ; Miyazawa, Flavio ; Wakabayashi, Yoshiko

• Tipo de documento: Artigo Científico
• Fonte: WALCOM: ALGORITHMS AND COMPUTATION, WALCOM 2022; v. 13174, p. 16-pg., 2022-01-01.

Resumo

For a constant t >= 1, a t-spanner of a connected graph G is a spanning subgraph of G in which the distance between any pair of vertices is at most t times its distance in G. We address two problems on spanners: the minimum t-spanner problem (MINSt), and a minimization version of the tree t-spanner problem (TREESt). MINSt seeks a t-spanner with minimum number of edges. TREESt is a decision problem concerning the existence of a t-spanner that is a tree. The concept of spanner was introduced by Peleg & Ullman in 1989, in a context regarding the construction of optimal synchronizers for the hypercube. MINSt is known to be NP-hard for every t >= 2 even on some bounded-degree graphs. TREESt is polynomially solvable for t >= 2 and NP-complete for t >= 4, but its complexity for t = 3 remains open. We investigate both MINS3 and TREES2 on the class of subcubic graphs. We prove that MINS3 can be solved in polynomial time, using a similar technique as the one used by Cai & Keil (1994) for t = 2. This result also gives an alternative algorithm to solve TREES3 in polynomial time. Additionally, we study TREES2 from a polyhedral point-of-view and show a complete linear characterization of the associated polytope. This result, interesting on its own right, gives a polynomial-time algorithm to solve a natural minimization version of TREES2 on subcubic graphs with costs assigned to its edges. (AU)

• Processo FAPESP: 19/14471-1 - Problemas sobre spanners em grafos
• Beneficiário: Renzo Gonzalo Gómez Diaz
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• Processo FAPESP: 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural
• Beneficiário: Flávio Keidi Miyazawa
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 16/01860-1 - Problemas de corte, empacotamento, dimensionamento de lotes, programação da produção, roteamento, localização e suas integrações em contextos industriais e logísticos
• Beneficiário: Reinaldo Morabito Neto
• Modalidade de apoio: Auxílio à Pesquisa - Temático