Jan Arne Trelle - "Recognition of Linear and Star Variants of Leaf Powers is in P"

A k-leaf power of a tree T is a graph G whose vertices are the leaves of T and whose edges connect pairs of leaves whose distance in T is at most k. A graph is a leaf power if it is a k-leaf power for some k. Over 20 years ago, Nishimura et al. [J. Algorithms, 2002] asked if recognition of leaf powers was in P. Recently, Lafond [SODA 2022] showed an XP algorithm when parameterized by k, while leaving the main question open. In this talk, I explore this question from the perspective of two alternative models of leaf powers, showing that both a linear and a star variant of leaf powers can be recognized in polynomial time.


© Università degli Studi di Roma "La Sapienza" - Piazzale Aldo Moro 5, 00185 Roma