%A Leal, Gustavo M.
%A Silva, Hebert C.
%A Longo, Humberto J.
%A Foulds, Les R.
%D 2024
%T Valid Paths, a short synthesis
%K
%X A labeling of a graph is an assignment of labels to its vertices and/or edges. The Path Validity Problem seeks to optimise the quantity of 2-paths with the integer label associated with the middle vertex being smaller than those associated with the path endpoints. Recent research has investigated the behaviour of optimal labeling in several classes of graphs. This work provides a summary overview of recent advances in the study of this challenging problem and presents that the decision problem of its maximising variant is NP-Complete, while its minimising variant remains an open problem.
%U https://sol.sbc.org.br/index.php/etc/article/view/29308
%J Anais do Encontro de Teoria da Computação (ETC)
%0 Journal Article
%R 10.5753/etc.2024.2539
%P 72-75%@ 2595-6116
%8 2024-07-21