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. Apr 3 '12 at 6:17
• But it would appropriate to ask on cstheory whether this is an open problem. 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. 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). Apr 6 '12 at 19:36

1 Answer

See Optimal algorithm for finding the girth of a sparse graph from cstheory.SE which has an accepted answer.

• I think answer in CSTheory is not complete, I'm waiting for more references so I didn't mark it as answer yet. But here you can decide to close this, but I'm not going to delete it because I think it's good to have history of this problem in CS. P.S: I know Shiva is excellent in related fields, but still I think it's better to leave it open, may be someone else has better references.
– user742
Apr 6 '12 at 19:45
• @SaeedAmiri: You might not always find a reference. It is possible that no one considered this problem before, or made an explicit note of it in some open problem list. You can always leave your question unmarked though. btw, I am against closing it here. This is a perfectly valid question for this site, and closing this might give the wrong impression to future questioners. Apr 6 '12 at 19:48
• take a look at the cstheory question now. Apr 6 '12 at 22:09
• See also Lecture on a Cycle in a Graph. Apr 14 '13 at 18:58