Finally, we mention that we are not aware of previous papers studying the complexity of problems when the input is restricted to have a high girth, but such questions were already studied in the context of graph spanners [1]}, [2]}.
