The $k$-in-a-tree problem for graphs of girth at least~$k$

Wei Liu, Nicolas Trotignon

For all integers $k\ge 3$, we give an $O(n^4)$ time algorithm for the problem whose instance is a graph $G$ of girth at least $k$ together with $k$ vertices and whose question is…