<p>Finding girth of a planar graph has an interesting history. See <a href="http://arxiv.org/abs/1104.4892" rel="nofollow">this paper</a> by Chang and Lu for a linear time algorithm and the history of improvements.</p>

<p>There is no general technique to find girth of <em>any</em> 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.</p>

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

CC BY-SA 3.0
2012-04-04T21:21:01.057Z
The planar paper seems interesting, thanks.
Saeed
CC BY-SA 3.0
2012-04-04T21:00:32.147Z
2012-04-04T21:00:32.147Z
Shiva Kintali
<p>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$.</p>

<p>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)$.</p>

<p>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.</p>

CC BY-SA 3.0
2012-04-06T22:07:59.473Z
awesome ! I was hoping the expert would show up :)
Suresh Venkat
CC BY-SA 3.0
2012-04-06T22:57:48.467Z
Virginia, what is a good reference for $O(m^{1.41})$ result? Is that by Yuster and Zwick?
Rachit
CC BY-SA 3.0
2012-04-07T01:13:50.163Z
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.
virgi
CC BY-SA 4.0
2018-10-26T22:26:18.423Z
There is a simple and general BFS-based O(nm) algorithm that I'm surprised nobody mentioned: https://webcourse.cs.technion.ac.il/234247/Winter2003-2004/ho/WCFiles/Girth.pdf
Labo
CC BY-SA 3.0
2012-04-06T21:55:02.750Z
2012-04-06T21:55:02.750Z
virgi
<p>I wonder how to find the <a href="http://en.wikipedia.org/wiki/Girth_%28graph_theory%29" rel="nofollow">girth</a> of a sparse undirected graph. By sparse I mean $|E|=O(|V|)$. By optimum I mean the lowest time complexity.</p>

<p>I thought about some modification on <a href="http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm" rel="nofollow">Tarjan's algorithm</a> 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.</p>

CC BY-SA 3.0
2012-04-04T15:51:34.633Z
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 :)
Suresh Venkat
CC BY-SA 3.0
2013-05-13T08:15:56.610Z
[copy](http://cs.stackexchange.com/questions/1001/optimal-algorithm-for-finding-the-girth-of-a-sparse-graph) on [cs.se].
Kaveh
CC BY-SA 3.0
2013-05-13T11:27:15.587Z
We don't directly leave comments on the FAQ entries, if you have a suggestion you can start a meta-discussion or post [here](http://meta.cstheory.stackexchange.com/questions/25/).
Kaveh
<ds.algorithms><graph-theory><open-problem>
Optimal algorithm for finding the girth of a sparse graph?
Saeed
# Optimal algorithm for finding the girth of a sparse graph?

(Asked by: username_0 on 2012-04-04)

I wonder how to find the [girth](http://en.wikipedia.org/wiki/Girth_%28graph_theory%29) 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](http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_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.

**Tags:** ds.algorithms, graph-theory, open-problem

> **Comments:**
> **username_1**: 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 :)  
> **username_2**: [copy](http://cs.stackexchange.com/questions/1001/optimal-algorithm-for-finding-the-girth-of-a-sparse-graph) on [cs.se].  
> **username_2**: We don't directly leave comments on the FAQ entries, if you have a suggestion you can start a meta-discussion or post [here](http://meta.cstheory.stackexchange.com/questions/25/).  

---

## 2 answers

### Answer by username_4 on 2012-04-06. Score: 28 | Accepted answer

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.

> **Comments:**
> **username_1**: awesome ! I was hoping the expert would show up :)  
> **username_5**: Virginia, what is a good reference for $O(m^{1.41})$ result? Is that by Yuster and Zwick?  
> **username_4**: 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.  
> **username_6**: There is a simple and general BFS-based O(nm) algorithm that I'm surprised nobody mentioned: https://webcourse.cs.technion.ac.il/234247/Winter2003-2004/ho/WCFiles/Girth.pdf  

---

### Answer by username_3 on 2012-04-04. Score: 5

Finding girth of a planar graph has an interesting history. See [this paper](http://arxiv.org/abs/1104.4892) 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.

> **Comments:**
> **username_0**: The planar paper seems interesting, thanks.  

---

