A polynomial-time algorithm recognizing exact cubes of trees

Procedia Computer Science. 2025. Vol. 273. P. 86–93.

Beaudou L., Echeverría H., Foucaud F., Jiménez A., Manuylenko N., Rachuri A.

We prove that the recognition of exact cubes of trees can be done in polynomial time. More precisely, the exact distance power of a graph is a refinement of the more usual notion of graph power. Given a graph G and a positive integer p, the exact distance pth power of G is the graph G#p on the same vertex set where two vertices are adjacent if their distance is exactly p in G. Recently Bai et al. [Y. Bai, P. P. Cortés, R. Naserasr and D. A. Quiroz. Characterizing and recognizing exact-distance squares of graphs. Discrete Mathematics 347(8). 2024] proved that the recognition of exact squares of trees is polynomially tractable. In order to extend this result to exact cubes of trees, we first test whether there is a caterpillar as an exact cubic root and, if not, proceed with a general tree. Both algorithms rely on the observation that the knowledge of a fixed number of vertices is roughly enough to deduce the whole structure of the tree we aim for.

Keywords: matchings, Exact distance power graphs

Publication based on the results of: New methods in the study of formal computation models, computer systems and related theoretical computer science problems (2025)