The kk-in-a-tree problem for graphs of girth at least kk

For all integers k≥3k≥3, we give an O(n4)O(n4)-time algorithm for the problem whose instance is a graph GG of girth at least kk together with kk vertices and whose question is “Does GG contains an induced subgraph containing the kk vertices and isomorphic to a tree?”.This directly follows for k=3k=3 from the three-in-a-tree algorithm of Chudnovsky and Seymour and for k=4k=4 from a result of Derhy, Picouleau and Trotignon. Here we solve the problem for k≥5k≥5. Our algorithm relies on a structural description of graphs of girth at least kk that do not contain an induced tree covering kk given vertices (k≥5k≥5).