13
$\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.

$\endgroup$
  • 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 '12 at 15:51
  • $\begingroup$ copy on Computer Science. $\endgroup$ – Kaveh May 13 '13 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 '13 at 11:27
23
$\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.

$\endgroup$
  • 5
    $\begingroup$ awesome ! I was hoping the expert would show up :) $\endgroup$ – Suresh Venkat Apr 6 '12 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 '12 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 '12 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 '18 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.

$\endgroup$
  • $\begingroup$ The planar paper seems interesting, thanks. $\endgroup$ – Saeed Apr 4 '12 at 21:21

Your Answer

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

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