# Algorithms on long paths and cycles in graphs

This thesis entitled: A lgorithms on Long Paths and Cycles in Graphs written by Shuxin Nie has been approved for the Department of Computer Science Harold Gabow Assist.Prof.San Skulrattanakulchai D ate The ﬁnal copy of this thesis has been examined by the signatories,and we ﬁnd that both the content and the form meet acceptable presentation standards of scholarly work in the above mentioned discipline.

iii N ie,Shuxin (Ph.D.,Computer Science) Algorithms on Long Paths and Cycles in Graphs Thesis directed by Prof.Harold Gabow Finding a longest path or cycle in a graph is a basic problem in graph theory. This problemis NP-hard since it has the Hamiltonian path or cycle problemas a special case.The thesis is working on ﬁnding good approximation algorithms in both directed and undirected graphs. In graph theory,n is always used to denote the number of vertices in the graph. For directed graphs,this thesis includes an algorithm that can ﬁnd a cycle of length at least log n/log log n in polynomial time,if one exists.Then it is generalized to an algorithm that can ﬁnd a vw-path of length at least log n/log log n in polynomial time, for two given vertices v,w of the graph.These are the best known results so far and the hardness results show that there is no polynomial time algorithm can ﬁnd a cycle of length ≥ log n under appropriate complexity assumption.The previously known technique of color coding can ﬁnd cycles of length exactly k,for any k ≤ log n,in poly time.However ﬁnding a cycle of length ≥ k is a much harder problem,e.g.it might require ﬁnding a Hamiltonian cycle. For undirected graphs,this thesis gives an algorithm that can ﬁnd a cycle of superpolylogarithmic length in polynomial time.ie,length exp(Θ( √ ℓ)),for ℓ the length of a longest cycle.It not only simpliﬁes Gabow’s algorithm in a previous work but also improves his result.As an indicator of the diﬃculty on this problem recall that the best hardness result proved to date is that an undirected cycle of length n/2 O(log 1−ǫ n) cannot be found in polynomial time,if NP DTIME(2 O(log 1/ǫ n) ),an assumption far stronger than P = NP. In the thesis we also extend the algorithms from ﬁnding simple cycles to ﬁnding

iv e dge simple closed walks,which is a ﬁeld no substantial results are proved before.The thesis includes a reduction from the latter problem to the cycle problem,showing that all algorithms on cycles can be used to ﬁnd edge simple closed walks.We also proved the same hardness results for both problems.

v A cknowledgements First of all,I thank my advisor,Hal Gabow.This dissertation and my accom- plishments during the Ph.D.study can’t complete without the guidance and help of him. He is so knowledgeable and patient,full of innovation ideas.He worked together with me on the algorithms included in the dissertation:both the directed cycle algorithms and undirected cycle algorithms. I also want to thank Richard Byrd,who is a member of my proposal and dis- sertation committees.Because of his suggestion,I started the work on chapter 3 and generalized the results in chapter 4.This work is on a not well-studied problem but the results turned out to be very exciting. Many thanks also goto the other members of my proposal and dissertation com- mittees:Andrzej Ehrenfeucht,Debra Goldberg,Michael Main and San Skulrattanakulchai. Thank you for your constructive comments and questions. Additionally,there are some other acknowledgments I’d like to make.Thanks to the reviewers of SODA 2004 and ACM Trans.on Algorithms,2008.They gave us valuable suggestions on our directed algorithm.Thanks to the reviewers of ISAAC 2008, they also gave us helpful comments. Finally,I want to thank my family,my parents and sister,and also my friends for their support and encouragement throughout my study.

Contents C hapter 1 Introduction 1 1.1 Previous Results...............................2 1.2 Our Contribution...............................5 1.3 Terminology..................................7 2 Directed Cycle Algorithms 9 2.1 Length Properties of Cycles.........................9 2.2 Directed Cycle Algorithm..........................11 2.3 Directed vw-Path Algorithm........................14 2.4 Summary...................................17 3 Reductions between Cycles and Circuits 19 3.1 Directed Graphs...............................19 3.2 Undirected Graphs..............................21 4 Undirected Algorithm 26 4.1 Approach of the Undirected Algorithm...................26 4.1.1 The Extend Step...........................27 4.1.2 Finding Separating Pairs......................33 4.2 Undirected S-circuit Algorithm.......................38

vii 4 .3 Length and Time Analysis..........................44 4.4 Hardness Results...............................51 5 Future Work 54 5.1 Long Undirected Cycle and Circuit Problems...............54 5.2 Hardness Results with Diﬀerent Assumptions...............55 5.3 Long Directed Path Problem........................56 5.4 Experimental Work..............................57 5.5 Cycle Packing Problem............................57 5.6 Cycle Cover Problem.............................58 Bibliography 60 Appendix A Finding a long directed cycle 64 A.1 Introduction..................................1 A.2 Depth-ﬁrst Search..............................5 A.3 Algorithms..................................14 A.4 Undirected Graphs..............................20 Bibliography 25 A.5 The Tight Lowpoint Cycle Theorem....................26 A.6 A Diameter-based Cycle Theorem.....................32 B Finding Long Paths,Cycles and Circuits 34 B.1 Introduction..................................1 B.2 Long Cycles Versus Long Circuits......................4

viii B .3 Algorithm for Undirected Graphs......................6 B.3.1 The Extend Step...........................9 B.3.2 Long Circuits Produce Separating Pairs..............14 B.4 Algorithm for Digraphs...........................16 Bibliography 20

ix F igures Figure 2.1 Lower bound graph for Theorem 2.1.1,when k ≥ 4.The path of 2k −5 solid edges forms the dfs tree,and the two dashed edges are not in the tree.10 2.2 The lowpoint cycle of edge (v,w),a is the ﬁrst ancestor of v in L w ....11 2.3 Lower bound graph for Theorem 2.1.2,when k ≥ 4.The solid edges form a dfs tree,the dashed edges are not in the tree.There are (k−2) 2 +k−3 tree edges,k −1 back edges and 1 cross edge................12 2.4 Illustration of the algorithm.Q intersects with C(a,b).We choose a v ∈ Q∩ C(a,b) with probability ≥ 1/(k 2 −k)...............13 2.5 The dashed path is a long vw-path with x the ﬁrst vertex of the tail. Q is a vx-path found by the algorithm.It can intersect with the tail at r,which make it possible that P doesn’t exist.Then the algorithm attempts to guess r..............................16 3.1 (a) The reduction froma vertex v ∈ V (G)−S to H v in H:H v is a directed bipartite graph;(b) The reduction from the directed circuit graph G to the directed cycle graph H:S vertices of G are drawn hollow.The subgraphs in dashed circles in H represent the vertices of G........20 3.2 (a) The circuit graph G and (b) the reduced cycle graph H.Each clique in a dashed circle in H represent one vertex of G..............22

x 3 .3 A graph with n vertices.The hollow vertex v 1 ∈ S and deg(v 0 ) = deg(v 1 ) = n −1,but a longest S-circuit has length 4............24 4.1 An (S,e)-circuit C and a connected component X of G C,S .c 0 ∈ S and c 1 ,d ∈ S.P is an S-trail recursively found in X..............28 4.2 An ES-block B,drawn dashed.Every circle represents an biconnected component.S vertices are drawn hollow, S solid.Any other two labeled vertices are E S-separated by B except the three pairs (x i ,y i ),i = 1,2,3.29 4.3 An xy-trail P and an xy-path Q.Every vertex of Q is on an equal length cycle in P.Every edge of Q is in P.QS = ∅.The longest circuit in P ∪Q has length (|P| −|Q|)/(|Q| +1)...................32 4.4 An (S,e)-circuit C with two connected components X of G C,S .Each component X has an ES-separating pair r 0 ,r 1 and a corresponding r 0 r 1 - trail P.The hollow vertex is in S.Each circle in the ﬁgure represents an ES-block....................................34 4.5 Finding a component cover on X:In this ﬁgure F 0 is not a star,F 1 is a star centered at r 1 ∈ S(C),and there are two possible r 0 :a vertex in S and an edge.The hollow vertices belong to S.Each circle in the ﬁgure represents an ES-block.The two B’s are b-round ES-blocks in X....37 4.6 The recursive calls of A:(a) Step 3.1 calls A p−1 .(b) Step 4.2 calls A p ..40 A.1 Lower bound graph for TheoremA.2.4,when k ≥ 4.The solid edges form a dfs tree,the dashed edges are not in the tree.There are (k−2) 2 +k−3 tree edges,k −1 back edges and 1 cross edge................8 A.2 Analysis of the long cycle C for Theorem A.2.4...............10 A.3 Lower bound graph for Theorem A.4.1,when k ≥ 4.The path of 2k −5 solid edges forms the dfs tree,and the two dashed edges are not in the tree.21 A.4 Analysis of the long cycle C for Theorem A.5.1...............27

xi B .1 A circuit C and connected component X of G C,S .c 1 and d belong to S. T he Extend Step combines the recursively found trail P with C e [c 0 ,c 1 ].8 B.2 An ES-block B,drawn dashed.Each solid circle represents a biconnected component that is not a bridge.S vertices are drawn hollow, S solid.Any two labelled vertices are E S-separated by B except for the pairs x i ,y i , i = 1,2,3...................................10 B.3 The dashed path is a long vw-path with x the ﬁrst vertex of the tail.Q is a vx-path found by the algorithm.If P doesn’t exist,Q intersects the tail,as illustrated by vertex r.The algorithm attempts to guess r....18

Chapter 1 I ntroduction Finding a longest path or cycle in a graph is a basic problemin graph theory.This is a diﬃcult problem because it is a general problem to the Hamiltonian path and cycle problems.Karp [32] in 1972 proved the NP-completeness of many famous problems in graph theory,which include the Hamiltonian cycle problem in both directed and undirected graphs. For these hard problems,the study on them have two directions.One is to ﬁnd good polynomial-time approximation algorithms while the goodness of the algorithms are measured by the approximation ratio to the optimal solution.The other is to prove the intractability of the problem,so called the hardness results,which give the lower bounds to the approximation ratios. People have been working hard on both directions.But there are still gaps be- tween the best known approximation ratios and hardness results,especially for undi- rected graphs.That’s why we are interested in these problems. This thesis includes our work on both directed and undirected problems.In graph theory,we always use n and m to denote the number of vertices and edges of a given graph,respectively.For directed graphs,we have a polynomial-time algorithm to ﬁnd a cycle of length ≥ log n/log log n.With a similar approach,for two given vertices v,w,we have another polynomial-time algorithm to ﬁnd a vw-path of length ≥ log n/log log n.

2 F or undirected graphs,our algorithm can ﬁnd a cycle of length exp(Ω √ log ℓ) i n polynomial time,where ℓ is the length of a longest cycle.We also generalize this algorithm so that it works for both vertex simple cycles and edge simple closed walks (circuits). Our results on both directed and undirected graphs are the best approximation algorithms so far.We also study the relations between cycles and circuits in both directed and undirected graphs.Our conclusion shows that all the algorithms for ﬁnding cycles can be used to ﬁnd circuits,although the approximation ratios may change for the undirected case. 1.1 Previous Results Monien [14] was the ﬁrst to work on ﬁxed parameter algorithms and he gave an algorithm that can ﬁnd paths and cycles of length exactly k in time 2 O(k log k) mn.This algorithm works for both directed and undirected graphs.It implies that a path or cycle of length log n/log log n can be found in polynomial time.Monien also proved a fact about the undirected cycle length:In an undirected graph with diameter d,if k ≥ 2d +2 then the existence of a cycle length ≥ k implies the existence of a cycle of length between k/2 and k.This is a useful property of cycles and allow us to check the existence of long cycles eﬃciently. Fellows and Langston [16] introduced the use of depth-ﬁrst search in this ﬁeld. They developed algorithms to ﬁnd undirected cycles of length ≥ k using Robertson- Seymour theorem [9],which classiﬁes the graphs containing no long cycles into a set with similar structures. Bodlaender [6] continued Fellows and Langston’s approach.His algorithm uses dynamic programming and can ﬁnd an undirected cycle or path of length ≥ k in time 2 O(k log k) n,which improved Monien’s time bounds. Alon,Yuster and Zwick [2] introduced the technique of color coding.It is a

3 r andomized algorithmto assign colors randomly to the vertices and ﬁnd a “colorful” path (every vertex on the path has a diﬀerent color) by dynamic programming.Color coding can be used to ﬁnd paths,cycles and other subgraphs (for example,paths with ﬁxed endpoints) of guaranteed size.This algorithm works on both directed and undirected graphs.It can ﬁnd a path of length ≥ log n in polynomial time.This is still the best result for directed graphs.For cycles,color coding ﬁnds a cycle of length exactly k,for k ≤ log n,in polynomial time,if one exists. Vishwanathan[44] and Bj¨orklund and Husfeldt [4] improved the results for undi- rected paths to beyond log n.Vishawnathan worked on Hamiltonian graphs,but the latter worked on general graphs and showed how to ﬁnd an undirected path of length Ω

( log ℓ/log log ℓ) 2

in polynomial time,for ℓ the length of a longest path.In [19] we observed that the length guarantee is actually Ω

log 2 ℓ/log log ℓ

. Gabow [11] used Bj¨orklund and Husfeldt’s idea but achieved much better results. His algorithmcan ﬁnd an undirected cycle of length exp

Ω(

log ℓ/log log ℓ)

through a given vertex in polynomial time.His algorithm can also be used to approximate the longest cycle,longest path and longest path through a given edge. Feder and Motwani [13] found a cycle of length exp(Ω( log n/log log n)) in Hamil- tonian graphs.Their results extend to graphs that are close to Hamiltonian (ℓ ≥ n/exp(o( √ log n log log n))) as well as some other cases. Better results are known for undirected graphs of low degree.Feder,Motwani and Subi [14] worked on graphs of maximum degree three.Their algorithm can ﬁnd a cycle of length ≥ ℓ log 9 2 > ℓ 0.315 in polynomial time,and ℓ is the longest cycle length. A similar result holds for longest path.The length guarantee improves on 3-connected cubic graphs (every vertex has degree 3).Jackson [29] proved that any two edges of a 3- connected cubic graph are contained in a cycle of length ≥ n log ( √ 5+1)−1 > n 0.69 .Chen, Xu and Yu [10] considered 3-connected graphs of maximum degree ∆.They proved that a cycle of length ≥ n log b 2 exists and can be found eﬃciently,for b = 2(∆−1) 2 +1.

4 I t’s simple to see that the Directed problems are more diﬃcult since every edge has a direction.Gabow and Nie [19] investigated long directed cycles.They found a directed cycle of length Ω( log n/log log n) in polynomial time,if such a cycle exists. This algorithmis based on depth-ﬁrst search.Bodlaender’s algorithm[6] does not apply to directed graphs since the depth-ﬁrst search on directed graphs produces diﬀerent types of nontree edges.Gabow and Nie studied the structure of directed cycles and make use of the depth-ﬁrst search tree to ﬁnd long directed cycles.They also proved a variant of Monien’s undirected cycle length theorem and the directed version of cycle length theorem:In a strongly connected graph with diameter d,for any k ≥ d the existence of a cycle length ≥ k implies the existence of a cycle of length between k and dk. Bj¨orklund,Husfeldt and Khanna [5] proved the best known hardness results on directed problems.They showed that no polynomial-time algorithm can ﬁnd a path or cycle of length ≥ n ǫ for any ǫ > 0 in a Hamiltonian directed graph,unless P = NP.If assuming the Exponential Time Hypothesis of [12],which says the 3-SAT problem,on instances of n variables,has no subexponential ( 2 o(n) ) time algorithm, they improved the lower bound for both directed paths and cycles.They proved that there is no polynomial-time algorithm to ﬁnd a directed path of length f(n) log 2 n,or a directed cycle of length f(n) log n with this assumption,for any function f that is ω(1), nondecreasing and computable in subexponential time.This shows the result from [19] may not be improved by more than a log log n factor. Hardness results for undirected problems are mush weaker.Karger,Motwani and Ramkumar [31] proved the best known hardness results on undirected problems. They showed that getting a constant factor approximation to the longest undirected path problem is NP-hard.Furthermore for any ǫ > 0,approximating to within a factor 2 O( log 1−ǫ n) is quasi-NP-hard.Quasi-NP-hard is the set of problems that cannot be solved in n poly log (n) time.Gabow’s algorithm [11] shrunk this gap,but it is still large.Bazgan,

5 S antha and Tuza [7] proved the same hardness results on cubic Hamiltonian graphs.The longest path problem remains one of the most basic problems whose approximability is not well-understood. There are other problems on cycles studied:ﬁnding an undirected cycle through speciﬁc number of given elements (vertices and edges).Robertson and Seymour [38] showed that more generally,the ﬁxed vertex subgraph homeomorphism problem can be solved in polynomial time.However huge constants are involved in this approach. LaPaugh and Rivest [34] developed linear time algorithm to ﬁnd a cycle through three given vertices with no large hidden constants.(See also [45].) We have ﬁnd polynomial algorithms to ﬁnd a cycle through three or four given elements,if such a cycle exists, with no large hidden constants.We also studied the patterns of the graphs with no such cycles. 1.2 Our Contribution We have worked on both directed and undirected graphs.In Chapter 2,this thesis gives an overview of our algorithms on directed graphs.We ﬁrst present our algorithm of ﬁnding a directed cycle of length ≥ log n/log log n in polynomial time,if such a cycle exists.We observe the structure of a depth-ﬁrst search tree of a graph that contains a desired cycle.Based on the property we found,we can use color coding and a randomized approach to ﬁnd a desired cycle.Then we show this randomized algorithm can be easily derandomized.The complete algorithm is given in the appendix A.Then we give a randomized algorithm to ﬁnd a directed vw-path of length ≥ log n/log log n in polynomial time.There is no properties on the length of vw-paths as for the cycles, but the randomized algorithm subtly avoid that. In Chapter 3,we observe the relations between cycles and circuits.Since we have studies the algorithm of ﬁnding cycles,we wish that those algorithms can also be used for ﬁnding circuits.We ﬁrst construct two reductions in digraphs in both directions:

6 f rom circuits to cycles and then from cycles to circuits.These reductions show that in digraphs,the problem of ﬁnding a longest cycle is equivalent to the problem of ﬁnding a longest circuit.This is also true for paths and trails in directed graphs.So we can use the results from Chapter 2 and apply them to circuits and trails. Then we turn to undirected graphs.There is only a reduction from the circuits to cycles.What’s more,if the maximum degree is large,the approximation algorithm for cycles won’t be a good algorithm for circuits.We present a simple algorithm to treat this case.This algorithm can ﬁnd a circuit of length ≥ ∆,for ∆ the maximum degree of the graph for circuits.Combining the reduction and this algorithm,we get an algorithm for ﬁnding circuits in undirected graphs. But the above algorithm for ﬁnding circuits won’t work for ﬁnding an S-circuit. For a set of vertices S,an S-circuit is a circuit that every vertex of S is visited at most once.In chapter 4,we present an algorithm that can ﬁnd an S-circuit of length exp(Ω( √ log ℓ)) in polynomial time,for ℓ the length of a longest S-circuit.When S = ∅, we ﬁnd a long circuit;when S contains every vertex of the given graph,we ﬁnd a long cycle. When the maximum degree of a graph is 3,any circuit is a simple cycle.So the hardness results for cycles also work for circuits.We then extend the results of [7] to the circuit problem. Even if we have make some progress in both directed and undirected problems, there are still big room to improve.In chapter 5,we give some directions that we will continue working on. Appendix A is the detailed directed cycle algorithm as [19].Appendix B gives the ISAAC submission of our undirected algorithm.It includes brieﬂy the contents in Chapter 3 and 4.

7 1 .3 Terminology All logarithms are base two unless noted otherwise.When used as a number,e is the base of natural logarithms.exp(x) denotes e x . Our graph terminology is consistent with [46] whenever possible.All graphs in next sections are simple.An element of a graph is a vertex or an edge.If H is a subgraph of G and S is a set of elements of G then S(H) denotes the set of elements of H that belong to S.(For instance if G = (V,E),the notation V (H) and E(H) have their usual meaning.) G[X] denotes the subgraph induced by vertex set X.For X and Y disjoint vertex sets,E[X,Y ] consists of all edges joining X and Y.Furthermore by convention writing xy ∈ E[X,Y ] means x ∈ X and y ∈ Y. A walk can have repeated vertices and edges.A vw-walk goes from vertex v to vertex w.A closed walk has its ﬁrst and last vertices identical.A path is a simple walk (it has no repeated vertices).A cycle is a simple closed walk.A trail is a walk with no repeated edges (it may have repeated vertices).A circuit is a closed walk with no repeated edges.For S a set of vertices,an S-trail is a trail that every vertex in set S can be visited at most once.An S-circuit is deﬁned similarly. For two vertices x = y,d(x,y) denotes the length of a shortest xy-path.If the graph of interest is unclear in some notation we include it as a subscript,e.g.,d G (x,y). If P is a trail we use P to denote a set of vertices or edges,as is convenient;|P| always denotes the number of edges in P. For any trail P,we arbitrarily choose one correct order of its edges (since it may contain repeated vertices,there can be multiple correct orders).Let x and y be two edges in P with x preceding y,then P[x,y] denotes the subtrail of P from x to y, x,y ∈ P[x,y].In an undirected graph,we occasionally write P[y,x] to refer to the subtrail from y to x in the reverse subtrail of P.If C is a circuit containing edges x,y and edge e then C e [x,y](C e [x ,y])denotes the subtrail of C from x to y that contains

8 ( avoids) e,respectively.We extend the subtrail notation to allow open-sided intervals, e.g.,P(x,y] is the trail P[x,y] −x. We extend the end of a trail from an edge to a vertex.If P[x,y] = x,P[z,y] with edge x = (u,v),z = (v,w),then P[u,y] = P[x,y],P(u,y] = P[z,y].vertex u may appear multiple times in P,so P[u,y] can represent any subtrail that ends with u and y.We arbitrarily choose one from these subtrails in this case.But when it’s clear which edge x is the ﬁrst edge of the subtrail that is incident with u,P[u,y] will only represent that subtrail.For two elements a,b,we say P is an a,b-trail if P is a trail ends with a and b.

Chapter 2 D irected Cycle Algorithms We call a cycle or path long if it contains at least k edges.In this chapter,we will give two algorithms.One is to ﬁnd a long directed cycle and the other is to ﬁnd a long directed vw-path for v,w two vertices of the graph.Note that the second algorithm is a generalized version of the ﬁrst algorithm,since we can ﬁnd a long cycle by searching for a vw-path for every edge (w,v) in the graph. For both problems,our algorithms may ﬁnd a much longer,even Hamiltonian, path or cycle.Observe this cannot be done by color coding:it can only ﬁnd a path or cycle of length exactly k. Both algorithms presented in this chapter are polynomial-time algorithms when k ≤ log n/log log n.We start by presenting the idea of our cycle algorithm. 2.1 Length Properties of Cycles Which type of graphs can contain a long cycle?We ﬁrst study the structure of cycles.For an undirected graph,we have found the following property: THEOREM 2.1.1 (Theorem 4.1 in [19]) In a connected undirected graph having a long cycle,either every dfs tree has a long fundamental cycle or some long cycle has at most 2k −4 edges. A fundamental cycle is the cycle formed from a spanning tree and a nontree edge.The proof is given in [19].Figure 2.1 shows the bound of the theorem is tight:

10 . . . k-3 . . . k-3 Figure 2.1:Lower bound graph for Theorem 2.1.1,when k ≥ 4.The path of 2k − 5 solid edges forms the dfs tree,and the two dashed edges are not in the tree. The two fundamental cycles have length (k −3) +1 +1 = k −1.The only other cycle is Hamiltonian and has length 2(1 +(k −3)) = 2k −4. We wish to ﬁnd a similar property for the directed case.And such a property exists.Let G be a strongly connected digraph since every cycle is entirely contained in a strongly connected component.Let T be an arbitrary depth-ﬁrst search tree of G.We deﬁne a “lowpoint cycle” based on the lowpoint values of Tarjan’s strong connectivity algorithm [15].r is the root of the tree.Each vertex is labelled by the order that it is visited by the tree.The label of r is 0.Each vertex v = r has a value lowpoint(v). lowpoint(v) is deﬁned as the lowest possible vertex y that is the head of a nontree edge (x,y) whose tail x descends from v.Strong connectivity implies that lowpoint(v) exists and in fact satisﬁes lowpoint(v) < v. Then,we can deﬁne lowpoint paths and lowpoint cycles.For vertex v,denote L v to be its lowpoint path from v to the root r.L v is deﬁned recursively as follows: L r is the length 0 path consisting of vertex r.If v = r and lowpoint(v) = y with corresponding edge (x,y) then L v = T[v,x],y,L y .

11 w a v Figure 2.2:The lowpoint cycle of edge (v,w),a is the ﬁrst ancestor of v in L w . T[v,x] is the tree path from v to x.(We may have v = x.If more than one vertex qualiﬁes as x the choice of x is arbitrary.) Let (v,w) be a nontree edge.Let a be the ﬁrst vertex in L w that is an ancestor of v.Deﬁne the lowpoint cycle of edge (v,w) (illustrated in Figure 2.2) by C vw = v,w,L w [w,a],T[a,v]. We check if the lowpoint cycles have a similar behaviour as the fundamental cycles in undirected graphs.We obtain the following property analogous to Theorem 2.1.1: THEOREM 2.1.2 (Theorem A.1 in [19]) In a strongly connected digraph having a long cycle,either every dfs tree has a long lowpoint cycle or some long cycle has at most (k −1)(k −2) edges. The proof of Theorem 2.1.2 is in Appendix A of [19].Figure 2.3 is an example to show this upper bound is tight.Each lowpoint cycle in the graph has length exactly k −1 and there is a Hamiltonian cycle of length (k −3) +1 +(k −2) 2 = (k −1)(k −2). 2.2 Directed Cycle Algorithm Now we give the algorithm of ﬁnding long directed cycles.Based on the result of Theorem 2.1.2,we can design the algorithm with two steps:

12 . . . k-2 ... ... . . k-3 ... . k-3 F igure 2.3:Lower bound graph for Theorem 2.1.2,when k ≥ 4.The solid edges form a dfs tree,the dashed edges are not in the tree.There are (k −2) 2 +k −3 tree edges, k −1 back edges and 1 cross edge. Step 1.Search for a long lowpoint cycle.If one is found return it,else continue; Step 2.Search for a cycle of length between k and k 2 .If one is found return it.If none is found declare there are no cycles of length ≥ k. Step 1 can be easily implemented.First build an arbitrary DFS tree.To make it eﬃcient to compute the lowpoint cycles,we ﬁrst compute the lowpoint value for every vertex and also label these vertices so that we can test if a given vertex descends from another in O(1) time [15,1].This preprocessing can all be done in O(m) time.Then we can just follow the deﬁnition to compute a lowpoint cycle C vw in time proportional to its length.Step 1 computes lowpoint cycles for every nontree edge,until either a long lowpoint cycle is found or all nontree edges are exhausted.There are less than m nontree edges,so clearly Step 1 takes total time O(km). Step 2 is implemented by a randomized approach.Suppose there is a cycle of length between k and k 2 ,then there exist two vertices a,b on this cycle and the cycle path from a to b has length exactly k.If we can ﬁnd the following two internal disjoint paths,a desired cycle is found:one path is from a to b of length exactly k and the other

13 ≤k −k a v b k Q 2 Figure 2.4:Illustration of the algorithm.Q intersects with C(a,b).We choose a v ∈ Q∩C(a,b) with probability ≥ 1/(k 2 −k) is a ba-path of length ≤ k 2 −k. Below is the pseudocode for Step 2.We ﬁrst guess the two vertices a and b.Then in each iteration,we will guess one new vertex on the length k ab-path.After k − 1 iterations,if all the vertices are guessed correctly,the correct ab-path is guaranteed to be found. choose 2 random vertices a,b ∈ V S ←∅ while |S| < k { Q ←a ba-path of length ≤ k 2 −k in G−S if Q does not exist then return “fail” P ←an ab-path of length k in G−Q+{a,b} if P exists then return cycle P,Q choose a random vertex v ∈ Q−{a,b} add v to S } Path Q is computed using breadth-ﬁrst search in O(m+n) time,and path P is computed by the color coding algorithm.The derandomized version uses 2 O(k) mlog n