14
$\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$
3
  • 1
    $\begingroup$ Virginia Vassilevska Williams and Ryan Williams have a paper showing that girth finding in general graphs is equivalent to APSP under subcubic transformations. I don't know if the relation holds for sparse graphs, but it does mean that going subquadratic might be hard. I'll let either of them post the details :) $\endgroup$
    – Suresh Venkat
    Apr 4, 2012 at 15:51
  • $\begingroup$ copy on Computer Science. $\endgroup$
    – Kaveh
    May 13, 2013 at 8:15
  • $\begingroup$ We don't directly leave comments on the FAQ entries, if you have a suggestion you can start a meta-discussion or post here. $\endgroup$
    – Kaveh
    May 13, 2013 at 11:27

2 Answers 2

Reset to default
28
$\begingroup$

Here's what I know about the girth problem in undirected unweighted graphs. First of all, if the girth is even, you can determine it in $O(n^2)$ time- this is an old result of Itai and Rodeh (A. Itai and M. Rodeh. Finding a minimum circuit in a graph. SIAM J. Computing, 7(4):413–423, 1978.). The idea there is: for each vertex in the graph, start a BFS until the first cycle is closed (then stop and move on to the next vertex); return the shortest cycle found. If the girth is even the shortest cycle found will be the shortest cycle. In particular if your graph is bipartite this will always compute the girth. If the girth $g$ is odd, however, you'll find a cycle of length $g$ or $g+1$, so you may be off by $1$.

Now, the real problem with odd girth is that inevitably your algorithm would have to be able to detect if the graph has a triangle. The best algorithms for that use matrix multiplication: $O($ min{$n^{2.38}, m^{1.41})$ time for graphs on $n$ nodes and $m$ edges. Itai and Rodeh also showed that any algorithm that can find a triangle in dense graphs can also compute the girth, so we have an $O(n^{2.38})$ time girth algorithm. However, the runtime for the girth in sparse graphs is not as good as that for finding triangles. The best we know in general is $O(mn)$. In particular, what seems to be the hardest is to find a $o(n^2)$ time algorithm for graphs with $m=O(n)$.

If you happen to care about approximation algorithms, Liam Roditty and I have a recent paper in SODA'12 on that: Liam Roditty, V. Vassilevska Williams: Subquadratic time approximation algorithms for the girth. SODA 2012: 833-845. There we show that a $2$-approximation can be found in subquadratic time, and some other results concerning additive approximations and extensions. Generally speaking, because of a theorem of Bondy and Simonovits, when you have densish graphs, say on $n^{1+1/k}$ edges, they already contain short even cycles, say roughly $2k$. So the denser the graph is, the easier it is to find a good approximation to the girth. When the graph is very sparse, the girth can be essentially arbitrarily large.

Improve this answer
$\endgroup$
4
  • 5
    $\begingroup$ awesome ! I was hoping the expert would show up :) $\endgroup$
    – Suresh Venkat
    Apr 6, 2012 at 22:07
  • $\begingroup$ Virginia, what is a good reference for $O(m^{1.41})$ result? Is that by Yuster and Zwick? $\endgroup$
    – Rachit
    Apr 6, 2012 at 22:57
  • 2
    $\begingroup$ The $O(m^{1.41})$ time triangle finding algorithm is in this paper: N. Alon, R. Yuster, U. Zwick. "Finding and counting given length cycles", Proc. ESA, 1994, pp. 354–-364. $\endgroup$
    – virgi
    Apr 7, 2012 at 1:13
  • $\begingroup$ There is a simple and general BFS-based O(nm) algorithm that I'm surprised nobody mentioned: webcourse.cs.technion.ac.il/234247/Winter2003-2004/ho/WCFiles/… $\endgroup$
    – Labo
    Oct 26, 2018 at 22:26
5
$\begingroup$

Finding girth of a planar graph has an interesting history. See this paper by Chang and Lu for a linear time algorithm and the history of improvements.

There is no general technique to find girth of any sparse graph. Often we have to look the associated special decompositions or embeddings to achieve better bounds. If a graph is "provably" sparse, there is often a nice structure associated with it. For example, bounded treewidth graphs are sparse and they have the associated tree decompositions.

Designing a $o(n^2)$ algorithm for general sparse graphs is an open problem.

Improve this answer
$\endgroup$
1
  • $\begingroup$ The planar paper seems interesting, thanks. $\endgroup$
    – Saeed
    Apr 4, 2012 at 21:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.