Tree 3-Spanners on Generalized Prisms of Graphs

Autor(es)

Gomez, Renzo ; Miyazawa, Flavio K. ; Wakabayashi, Yoshiko

• Tipo de documento: Artigo Científico
• Fonte: LATIN 2022: THEORETICAL INFORMATICS; v. 13568, p. 17-pg., 2022-01-01.

Resumo

Let t >= 1 be a rational constant. A t-spanner of a graph G is a spanning subgraph of G in which the distance between any pair of vertices is at most t times their distance in G. This concept was introduced by Peleg & Ullman in 1989, in the study of optimal synchronizers for the hypercube. Since then, spanners have been used in multiple applications, especially in communication networks, motion planning and distributed systems. The problem of finding a t-spanner with the minimum number of edges is NP-hard for every t >= 2. Cai & Corneil, in 1995, introduced the Tree t-SPANNER PROBLEM (TREESt), that asks whether a given graph admits a tree t-spanner (a t-spanner that is a tree). They showed that TREESt can be solved in linear time when t = 2, and is NP-complete when t >= 4. The case t = 3 has not been settled yet, being a challenging problem. The prism of a graph G is the graph obtained by considering two copies of G, and by linking its corresponding vertices by an edge (also defined as the Cartesian product G x K-2). Couto & Cunha (2021) showed that TREESt is NP-complete even on this class of graphs, when t >= 5. We investigate TREES3 on prisms of graphs, and characterize those that admit a tree 3-spanner. As a result, we obtain a linear-time algorithm for TREES3 (and the corresponding search problem) on this class of graphs. We also study a partition of the edges of a graph related to the distance condition imposed by a t-spanner, and derive a necessary condition -checkable in polynomial time- for the existence of a tree t-spanner on an arbitrary graph. As a consequence, we show that TREES3 can be solved in polynomial time on the class of generalized prisms of trees. (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