# Optimal algorithm for finding the girth of a sparse graph?

I wonder how to find the girth of a sparse undirected graph. By sparse I mean $|E|=O(|V|)$. By optimum I mean the lowest time complexity.

I thought about some modification on Tarjan's algorithm for undirected graphs, but I didn't find good results. Actually I thought that if I could find a 2-connected components in $O(|V|)$, then I can find the girth, by some sort of induction which can be achieved from the first part. I may be on the wrong track, though. Any algorithm asymptotically better than $\Theta(|V|^2)$ (i.e. $o(|V|^2)$) is welcome.

• This is probably still an open problem and perhaps better suited for cstheory. – Aryabhata Apr 3 '12 at 6:17
• But it would appropriate to ask on cstheory whether this is an open problem. – JeffE Apr 3 '12 at 8:01
• @Suresh, I can't think better than $\Omega(n^2)$ for BFS. Also if this is suited for CStheory I'll ask it there tomorrow. – user742 Apr 3 '12 at 9:50
• Note: this question has been transferred to cstheory. Voting to close. – Suresh Apr 6 '12 at 15:48
• @Suresh: Rather than closing, we should just add an answer here with a link to the answer there, saying it was answered in cstheory. Besides, what would we close it as? Off-topic? (I have added a CW answer). – Aryabhata Apr 6 '12 at 19:36