New Subquadratic Approximation Algorithms for the Girth
Søren Dahlgaard∗1 , Mathias Bæk Tejs Knudsen1 , and Morten Stöckel†1
1

University of Copenhagen, [soerend,knudsen,most]@di.ku.dk

arXiv:1704.02178v1 [cs.DS] 7 Apr 2017

Abstract
We consider the problem of approximating the girth, g, of an unweighted and undirected
graph G “ pV, Eq with n nodes and m edges. A seminal result of Itai and Rodeh [SICOMP’78]
gave an additive 1-approximation in Opn2 q time, and the main open question is thus how
well we can do in subquadratic time.
In this paper we present two main results. The first is a p1 ` ε, Op1qq-approximation in
truly subquadratic
Q
U time. Specifically, for any k ě 2 our algorithm returns a cycle of length
g
2 rg{2s ` 2 2pk´1q in Õpn2´1{k q time. This generalizes the results of Lingas and Lundell
[IPL’09] who showed it for the special case of k “ 2 and Roditty and Vassilevska Williams
[SODA’12] who showed it for k “ 3. Our second result is to present an Op1q-approximation
running in Opn1`ε q time for any ε ą 0. Prior to this work the fastest constant-factor
approximation was the Õpn3{2 q time 8{3-approximation of Lingas and Lundell [IPL’09] using
the algorithm corresponding to the special case k “ 2 of our first result.

1

Introduction

In this paper we consider the basic graph theoretical problem of computing the shortest cycle of
an unweighted and undirected graph. The length of this cycle, g, is also known as the girth of a
graph.
Computing the girth of a graph has been studied since the 1970s. In a seminal paper from
1978, Itai and Rodeh [5] showed that the girth of an n-node, m-edge graph can be computed
in Opnω q time using fast matrix multiplication, where ω ă 2.373 is the matrix multiplication
constant [4]. They also observed that running n breadth first searches gives an Opmnq time
combinatorial algorithm for finding the girth. Here combinatorial means an algorithm that
does not employ Strassen-like cancellation tricks and arithmetic operations over some field.
Furthermore, it was shown by Vassilevska Williams and Williams [11] that any combinatorial
algorithm computing the girth in Opn3´ε q for any ε ą 0 would imply a truly subcubic algorithm
(i.e. Opn3´ε q for some ε ą 0) for combinatorial boolean matrix multiplication. Obtaining such
an algorithm is widely conjectured to be impossible.
This seeming barrier, combined with fast matrix multiplication being deemed impractical,
motivates the study of approximation algorithms for the girth, g. In the paper of Itai and
Rodeh [5] they also presented an algorithm computing a cycle of length at most g ` 1 in Opn2 q
time using a simple BFS approach. In some sense this is an optimal approximation algorithm, as
the input may indeed be as large as Θpn2 q and we cannot hope to get a better approximation.
However, we also know due to a classic result by Bondy and Simonovits [2] that any undirected
∗

Research partly supported by Mikkel Thorup’s Advanced Grant DFF-0602-02499B from the Danish Council
for Independent Research under the Sapere Aude research career programme.
†
Research partly supported by Villum Fonden.

1

graph with more than 200n3{2 edges contains a 4-cycle. Furthermore, we can find such a cycle in
Opnq expected time using the subroutine of Yuster and Zwick [12] giving an Opnq time algorithm
returning a cycle of length at most g ` 1 for graphs with many edges (since g ě 3). It thus
remains interesting to obtain approximation algorithms with subquadratic running time.
This problem was initially studied by Lingas and Lundell [6] and later by Roditty and
Vassilevska Williams [10]. In this paper we say that an algorithm is a pc1 , c2 q-approximation
to the girth for c1 ě 1, c2 ě 0, if the algorithm returns a cycle with length g̃ such that
g ď g̃ ď c1 ¨ g ` c2 . We say that a pc1 , 0q-approximation is a multiplicative c1 -approximation
(or just c1 -approximation), and that a p1, c2 q-approximation is an additive c2 -approximation
(or just `c2 ´ approximation). Lingas and Lundell [6] initialized the study of subquadratic
girth approximation
algorithms by giving a Monte Carlo p2, 2q-approximation in expected time
?
3{2
Opn
log nq. It is worth noting that this algorithm represents an (at worst) 8{3-approximation.
They stated as an open question whether a subquadratic time algorithm giving a multiplicative
approximation factor of two or better exists. This question was answered by Roditty and
Vassilevska Williams [10] who presented several subquadratic approximation algorithms for the
girth. In particular they gave a 2-approximation in Opn5{3 log nq time. In fact, they showed a
more general result returning a cycle of length at most 2 rg{2s`2 rg{4s (although they state it quite
differently)1 in Opn5{3 log nq. This can be seen as an “almost-but-not-quite” 3{2-approximation.
They also conjecture that obtaining a p2 ´ εq-approximation requires essentially quadratic time.
Complementing this conjecture, they present a randomized algorithm which beats this barrier
for triangle-free graphs, giving an 8{5-approximation in Opn1.968 q which can be improved to
Opn1.942 q using the result of [3] as a lemma. Finally, in the same paper, Roditty and Vassilevska
Williams present an additive 3-approximation (additive 2 for even g) in time Opn3 {m log2 nq.

1.1

Our contribution

In this paper we address the following two questions: “How good an approximation can we give
for the girth in subquadratic time?” and “What is the fastest running time of any constant-factor
approximation algorithm to the girth?”.
The conjecture of Roditty and Vassilevska Williams [10] suggests that we cannot hope to
obtain a p2 ´ εq-approximation faster than Ωpn2 q. However, we show that if we allow a small
additive error, we can an arbitrarily good multiplicative approximation in subquadratic time –
that is, a p1 ` ε, Op1qq-approximation for any ε ą 0. Specifically, we show the following theorem.
Theorem 1. Let G be a graph with
n nodes and let ˘k ě 2 be any integer. Then there exists
` 2´1{k
an algorithm
that
runs
in
time
O
n
plog nq1´1{k and finds a cycle with length at most
Q
U
PgT
g
2 2 ` 2 2pk´1q
, where g is the girth of G.
Theorem 1 generalizes the result of Roditty and Vassilevska Williams [10, Thm. 1.3], who
showed it for the special case of k “ 3 (with an additional log1{3 n factor) and the result of Lingas
and Lundell [6, Thm. 1] who showed a Monte Carlo version for the special case of k “ 2. As a
corollary, we also get an improvement on the result for triangle-free graphs [10, 3] improving the
running time from Opn1.942 q to Opn9{5 log4{5 nq and generalizing to families of graph with girth
g ą 2` ´ 1 for any positive integer `.
P T
Corollary 1. Let ` be a positive integer and k “ 2` ´ 3` ` 2. There exists an algorithm
`
˘
that given a graph G with n nodes and girth ą 2` ´ 1 runs in time O n2´1{k and gives a
3
p1 ` 2``1
q-approximation of the girth.
1

For a graph with girth g “ 4c ´ z for some c ě 1 and z P t0, 1, 2, 3u their algorithm returns a cycle of length
6c ´ z for even g and 6c ´ z ` 1 for odd g. It can be verified by inspection that this is indeed 2 rg{2s ` 2 rg{4s.

2

For completeness we show how Theorem 1 directly implies Corollary 1 above in Appendix A.
Complementing Theorem 1, we also show that for any constant ε ą 0 it is possible to obtain
a constant-factor approximation in Opn1`ε q expected time. Specifically, we show the following
theorem.
Theorem 2. Let G be a graph with n nodes and k an integer ě 2. There exists an algorithm
giving a 2k -approximation to the girth of G with probability 1 ´ n1 running in expected time
`
˘
O n1`1{k k log n .
Our algorithms are quite simple and rely on sampling and a “stop-early” BFS procedure
similar to previous work [5, 6, 10]. Using techniques of [10] it is possible to derandomize the
sampling in Theorem 1, however this procedure is too slow and does not work for Theorem 2,
hence this theorem is only available in a randomized variant.

1.2

Related work

The problem of approximating the girth has also been considered in other settings. For undirected
graphs with weights in t1, . . . , M u Lingas and Lundell [6] gave a 2-approximation of the minimum
weight cycle running in Opn2 log nplog n ` log M qq. Roditty and Tov [8] improved the approximation factor to 4{3 while maintaining the running time, and also gave a Op 1ε n2 log n log log nq
time p4{3 ` εq-approximation for graphs with non-negative real weights. Furthermore, it was
shown by Roditty and Vassilevska Williams [9] that the problem (also for directed graphs)
reduces to finding a minimum weight triangle in an undirected graph with Opnq nodes and
weights in t1, . . . , OpM qu. For directed graphs a recent paper by Pachocki, et al. [7] gave a
Opk log nq-approximation in Opmn1{k log5 nq for any k ě 1 and an additive Opnα q-approximation
in Opmn1´α q for any α P p0, 1q.
Closely related to the problem of finding the girth of a graph is the problem of finding a
cycle of a fixed length k. For undirected graphs, Yuster and Zwick [12] showed that this can
be done for even k in Opf pkq ¨ n2 q. Alon, Yuster and Zwick [1] showed that for directed and
undirected graphs this can be done in Opf pkq ¨ m2´2{k q if k is even and Opf pkq ¨ m2´2{pk`1q q if
k is odd. And for undirected graphs when k is even they give an algorithm with running time
´1
Opm2´p1`rk{4s q{pk{2`1q q. For even k this was improved [3] to Opf pkq ¨ m2´4{pk`2q q. This problem
of finding an even k-cycle was used as a subroutine by Roditty and Vassilevska Williams [10] in
some of their algorithms for approximating the girth.

2

Preliminaries

We will assume that all graphs G “ pV, Eq in the paper are undirected, unweighted, connected
and contain at least one cycle. If u is some node in the graph G and ` is an integer, we denote
by BG pu, `q the ball of radius ` around u in G, i.e. the set of all nodes of distance at most `
from u in G. We will sometimes denote this simply Bpu, `q when G is clear from the context.
We let Γpuq denote
the neighbourhood of u, i.e. Γpuq “ Bpu, 1qz tuu. For a set of nodes S Ď V ,
Ť
let BpS, `q “ uPS Bpu, `q. We denote by C` the simple cycle of length ` and let log x be the
natural logarithm of x.
We will need the following lemma, which was used in a slightly weaker version by Roditty
and Vassilevska Williams [10]
Lemma 1. Let A1 , . . . , Ak be sets over a universe U of n elements such that for every i ď k we
have |Ai | “ x for some positive x. Then we can find a set S Ď U with |S| ď nx log k in Opkx ` nq
time such that for each 1 ď i ď k we have S X Ai ‰ H.
3

Proof. Let tpuq “ |ti | u P Ai u|. We start by computing this quantity for each u P U in Opkx ` nq
time by simply traversing all the sets Ai . We now keep k linked lists L1 , . . . , Lk , where Li
contains the elements u such that tpuq “ i. In addition, we keep a table T where T rus contains a
pointer to the node in L1 , . . . , Lk containing u.
The algorithm now works as follows. Let S “ H. Repeatedly find an element u with
maximum tpuq, add it to S, and for each remaining Ai such that u P Ai , we remove Ai and
for each v P Ai update tpvq to tpvq ´ 1 and move it from Ltpvq to Ltpvq´1 . We note that we
may update an element v several times, and that if tpvq becomes 0 we simply ignore v for the
remainder of the algorithm.
Since the maximum value tpuq can never decrease we can keep track of the maximum value
in total Opkq time over all iterations. Furthermore, all updates take Opkxq time using the lists
L1 , . . . , Lk and our table T . The analysis of the size of S now follows exactly as in [10].
Similar to previous papers [5, 10, 6] we will use a procedure called BFS-CyclepG, uq, which
is simply the algorithm which runs a BFS from u in G until a node v is visited twice. In this
case the algorithm returns the simple cycle containing v in the BFS tree including the last edge
visited. We will need the following well-known lemma from the literature.
Lemma 2. [[5, 6]] Let G “ pV, Eq and let u P V be any vertex. Then running BFS-CyclepG, uq
takes Opnq time. Furthermore, if v is a vertex at distance ` from u and v is contained in a simple
cycle of length k, then BFS-CyclepG, uq returns a cycle of length at most 2 rk{2s ` 2`.
Sometimes we will need to run a restricted version of BFS-Cycle which stops after visiting
a certain number of nodes (or if a cycle was found before). Let this procedure be denoted
by BFS-CyclepG, u, yq, where y is the bound on the number of visited nodes. It is clear that
BFS-CyclepG, u, yq takes at most Opyq time if we assume an adjacency list representation.
We will need the following algorithm, which samples a set S and runs BFS-Cycle from each
u P S.
Definition 1. Let ApG, x, yq be an algorithm that takes an n-node graph G “ pV, Eq and two
positive numbers x, y. The algorithm creates
( a set S Ď V of nodes by sampling each node of V
x
independently with probability min n , 1 . Clearly S has expected size x. The algorithm then
runs BFS-CyclepG, u, yq for each u P S and returns the smallest cycle found or nothing if no
cycle is found.
We will also need the following deterministic variant, where the set S is picked using Lemma 1.
Definition 2. Let Adet pG, x, yq be the same algorithm as ApG, x, yq with the following modifin
cation to how the set S is picked. Fix x̃ “ n log
and denote the nodes of G by u1 , . . . , un . The
x
algorithm first creates the sets A1 , . . . , An , where Ai is the set containing the x̃ closest nodes
to ui (breaking ties arbitrarily, eg. by the order in the adjacency lists). It then creates the set
S Ď V by running the algorithm of Lemma 1 on A1 , . . . , An .
It´ is easy to see
¯ that ApG, x, yq runs in Opn ` xyq expected time and that Adet pG, x, yq runs
n2 log n
in O
` xy time.
x

3

Subquadratic girth approximations

In this section we present our algorithm for obtaining subquadratic approximations of the girth.
In particular we will prove Theorem 1.

4

Proof of Theorem 1. Let x be some parameter to be defined later. We run two algorithms
and ´take the smallest
cycle produced by the two algorithms. The first algorithm is simply
¯
n log n
Adet G, x , n of Definition 1. The second algorithm is the following. For each node u P V
we calculate the largest integer rpuq such that |Bpu, rpuqq| ď x. Let u1 , . . . , un denote the nodes
of G in sorted order such that rpu1 q ě . . . ě rpun q. We initialize an empty graph H. For each
i “ 1, 2, . . . , n in order such that rpui q ą 0 we add ui to H along with edges tu1 , . . . , ui´1 uXΓpui q
n
and run BFS-CyclepH, ui , n log
x q keeping track of the smallest cycle seen this far. The output of
our algorithm is the smallest cycle produced by any of the above steps.
U
Q
g
It remains to prove that the algorithm returns a cycle of length at most 2 rg{2s ` 2 2pk´1q
.
Let C be a cycle of length g in G and let t “ minuPC trpuqu. We know that the set S produced
n
by Adet pG, n log
x , nq contains a node with distance at most t ` 1 to C and therefore, by Lemma 2,
this algorithm returns a cycle with
U at most 2 rg{2s ` 2pt ` 1q. It follows Qthat the
U call to
Q length
n log n
g
g
Adet pG, x , nq suffices for t ă 2pk´1q . Now, assume that t ě t0 , where t0 “ 2pk´1q and let
u be the last node of C that was added to H. Let Hu denote the graph H after adding u. It
follows by the definition of u that the cycle C is contained in Hu . Furthermore, for each v P Hu we
have rpvq ě rpuq ě t0 and thus |BHu pv, t0 q| ď x. This implies that |BHu pv, pk ´ 1qt0 q| ď xk´1 for
each v P Hu and since pk ´ 1qt0 ě rg{2s by assumption, this implies that |BHu pu, rg{2sq| ď xk´1 .
We can now use Lemma 2 to conclude that the call to BFS-CyclepHu , u, xk´1 q returns a cycle of
length at most 2 rg{2s.
For the running time of the algorithm observe first that we can find rpuq for each u in Opxq
time using a BFS. Furthermore, since we only add nodes ui to H when rpui q ą 0 it follows that
we´ only consider at most
Opnxq edges for addition to H. The running time is now bounded by
¯
n log n
k´1
O n ¨ x ` nx
, which is minimized when x “ pn log nq1{k giving a total running time of
Opn2´1{k plog nq1´1{k q.

4

Constant approximation in near-linear time

We will now show how to obtain a constant factor approximation randomized in near-linear time.
Proof of Theorem 2. The algorithm is very straight-forward: For each i “ 1, . . . , k we run
ApG, n1`p1´iq{k log n, ni{k q and return the minimal cycle found or nothing if no cycle is reported.
We now analyze this procedure. Let g be the girth of G and C a cycle in G with length g.
Let r be the smallest non-negative integer such that
|B pC, rg{2s ¨ p2r ´ 1qq| ď nr{k .
Clearly such an r exists, as we may pick r “ k. Also observe that r ą 0 since, in particular, the
ball with r “ 0 contains the cycle C itself. We will show that the rth iteration of the algorithm
gives a sufficiently small cycle. Consider the algorithm ApG, n1`p1´rq{k log n, nr{k q and let S be
the set of nodes sampled by this algorithm. We will show that there exists a node u P S close to
C, such that C` is contained in the ˘tree explored by BFS-CyclepG, u, nr{k q. Consider the slightly
smaller ball B C, rg{2s ¨ p2r´1 ´ 1q . By the minimality of r, the number of nodes in S belonging
to this ball in expectation is at least
ˇ `
˘ˇ
ˇB C, rg{2s ¨ p2r´1 ´ 1q ˇ ¨ np1´rq{k log n ě npr´1q{k ¨ np1´rq{k log n “ log n .
`
˘
Therefore the probability that no node from B C, rg{2s ¨ p2r´1 ´ 1q is sampled is at most n1 .
We thus assume that such a sampled node, u, exists. We now argue that the BFS search
starting in u gives the desired cycle. This is illustrated in Figure 1. Since u is contained in
5

≤ ⌈g/2⌉

C
≤ ⌈g/2⌉⋅(2r-1-1)

u

Figure 1: Illustration of the proof of Theorem 2. u is a sampled node, and running BFS-Cycle
from u visiting at most nr{k gives the desired approximation.
`
˘
B C, rg{2s ¨ p2r´1 ´ 1q we know that Bpu, rg{2s 2r´1 q Ď B pC, rg{2s ¨ p2r ´ 1qq and thus, by
ˇ
ˇ
the definition of r, we know that ˇBpu, rg{2s 2r´1 qˇ ď nr{k . Furthermore, this ball around u
also contains the cycle C and thus ApG, n1`p1´rq{k log n, nr{k q returns a cycle of length at most
2 ¨ rg{2s ¨ 2r´1 . Since r ď k the length of the cycle returned is at most 2k rg{2s.
Since we invoke that algorithm A exactly k times and each invocation takes Opn1`1{k log nq
in expectation the running time follows.
We note that we cannot employ the algorithm Adet instead in the algorithm above, as the
task of creating a ball around each node u P V in order to employ Lemma 1 takes too long. This
is the main bottle-neck in obtaining a deterministic variant of Theorem 2.

5

Conclusion and open problems

In this paper we have studied the problem of obtaining subquadratic approximation algorithms for
the girth of an undirected and unweighted graph. We have shown how to obtain a multiplicative
p1 ` εq-approximation with small additive error in subquadratic time, and an Op1q-approximation
in Opn1`ε q time for any ε ą 0. It remains as the main open question whether one can obtain
a multiplicative p2 ´ εq-approximation in Opn2´ε q time or perhaps show that obtaining such
an approximation requires n2´op1q using the framework of Hardness in P. Another interesting
question is whether one can improve on our Theorem 2 and obtain a multiplicative Op1qapproximation in n1`op1q time or an additive Op1q-approximation in Opn2´ε q time. Finally, it
is an interesting question whether one can improve on Corollary 1 and obtain a multiplicative
3
p1 ` 2``1
´ εq-approximation in subquadratic time for graphs with girth ą 2` ´ 1.

References
[1] Noga Alon, Raphael Yuster, and Uri Zwick. Finding and counting given length cycles.
Algorithmica, 17(3):209–223, 1997. See also ESA’94.
[2] John A. Bondy and Miklós Simonovits. Cycles of even length in graphs. Journal of
Combinatorial Theory, Series B, 16(2):97 – 105, 1974.
[3] Søren Dahlgaard, Mathias Bæk Tejs Knudsen, and Morten Stöckel. Finding even cycles
faster via capped k-walks. CoRR, abs/1703.10380, 2017. To appear at STOC’2017.

6

[4] François Le Gall. Powers of tensors and fast matrix multiplication. In Proc. 39th International
Symposium on Symbolic and Algebraic Computation (ISSAC), pages 296–303, 2014.
[5] Alon Itai and Michael Rodeh. Finding a minimum circuit in a graph. SIAM Journal on
Computing, 7(4):413–423, 1978.
[6] Andrzej Lingas and Eva-Marta Lundell. Efficient approximation algorithms for shortest
cycles in undirected graphs. Information Processing Letters, 109(10):493–498, 2009.
[7] Jakub Pachocki, Liam Roditty, Aaron Sidford, Roei Tov, and Virginia Vassilevska Williams.
Approximating cycles in directed graphs: Fast algorithms for girth and roundtrip spanners.
CoRR, abs/1611.00721, 2016.
[8] Liam Roditty and Roei Tov. Approximating the girth. ACM Transactions on Algorithms,
9(2):15:1–15:13, 2013. See also SODA’11.
[9] Liam Roditty and Virginia Vassilevska Williams. Minimum weight cycles and triangles:
Equivalences and algorithms. In Proc. 52nd IEEE Symposium on Foundations of Computer
Science (FOCS), pages 180–189, 2011.
[10] Liam Roditty and Virginia Vassilevska Williams. Subquadratic time approximation algorithms for the girth. In Proc. 23rd ACM/SIAM Symposium on Discrete Algorithms (SODA),
pages 833–845, 2012.
[11] Virginia Vassilevska Williams and Ryan Williams. Subcubic equivalences between path,
matrix and triangle problems. In Proc. 51st IEEE Symposium on Foundations of Computer
Science (FOCS), pages 645–654, 2010.
[12] Raphael Yuster and Uri Zwick. Finding even cycles even faster. SIAM Journal on Discrete
Mathematics, 10(2):209–222, 1997. See also ICALP’94.

7

Appendix
A

Omitted proofs

Proof
of Corollary
1. We use Theorem 1 with k “ 2` ´
¯
´
3
-approximation we just need to prove that
1 ` 2``1
2

PgT
2

Q
`2

g
2pk´1q

P`T
3

` 2. In order to prove that we get a

U

g

ď1`

3
,
2` ` 1

(1)

whenever g ě 2`. For g “ 2` (1) holds, so assume that g ě 2` `Q1.
U
P T
g
“ 2. Therefore:
For 2` ` 1 ď g ď 2pk ´ 1q we note that 2 g2 ď g ` 1 and 2 2pk´1q
2

PgT
2

Q

g
2pk´1q

`2

U

g

ď

g`3
3
3
“1` ď1`
,
g
g
2` ` 1

and (1) holds. So assume that g ą 2pk ´ 1q. Then we can write g as g “P 2pk
T ´ 1qq ` r for some
g
positive
Q
Uinteger q and some r P t1, 2, . . . , 2pk ´ 1qu. We again use that 2 2 ď g ` 1 and see that
g
2pk´1q

“ q ` 1. So we get that:
2

PgT
2

Q
`2

g
2pk´1q

g

U
ď

g ` 1 ` 2q ` 2
3 ` 2q
3 ` 2q
“1`
ď1`
.
g
g
2pk ´ 1qq ` 1

The right hand side of (2) is maximized when q “ 1, and therefore we get:
Q
U
P T
g
2 g2 ` 2 2pk´1q
5
ď1`
,
g
2k ´ 1
and therefore we just need to prove that

But we have that

P`T
3

ď

5
2k´1

ď

kě

5` ` 4
.
3

``2
3

3
2``1 .

This can be rewritten as

and therefore
R V
`
``2
5` ` 4
k “ 2` ´
` 2 ě 2` ´
`2“
,
3
3
3

as desired.

8

(2)

