20
$\begingroup$

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.

Improve this question
$\endgroup$
9
  • $\begingroup$ This is probably still an open problem and perhaps better suited for cstheory. $\endgroup$
    – Aryabhata
    Apr 3, 2012 at 6:17
  • 6
    $\begingroup$ But it would appropriate to ask on cstheory whether this is an open problem. $\endgroup$
    – JeffE
    Apr 3, 2012 at 8:01
  • 1
    $\begingroup$ @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. $\endgroup$
    – user742
    Apr 3, 2012 at 9:50
  • 1
    $\begingroup$ Note: this question has been transferred to cstheory. Voting to close. $\endgroup$
    – Suresh
    Apr 6, 2012 at 15:48
  • 2
    $\begingroup$ @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). $\endgroup$
    – Aryabhata
    Apr 6, 2012 at 19:36

1 Answer 1

Reset to default
7
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – user742
    Apr 6, 2012 at 19:45
  • $\begingroup$ @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. $\endgroup$
    – Aryabhata
    Apr 6, 2012 at 19:48
  • 1
    $\begingroup$ take a look at the cstheory question now. $\endgroup$
    – Suresh
    Apr 6, 2012 at 22:09
  • 1
    $\begingroup$ See also Lecture on a Cycle in a Graph. $\endgroup$
    – Pål GD
    Apr 14, 2013 at 18:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy