• unlimited access with print and download
    $ 37 00
  • read full document, no print or download, expires after 72 hours
    $ 4 99
More info
Unlimited access including download and printing, plus availability for reading and annotating in your in your Udini library.
  • Access to this article in your Udini library for 72 hours from purchase.
  • The article will not be available for download or print.
  • Upgrade to the full version of this document at a reduced price.
  • Your trial access payment is credited when purchasing the full version.
Buy
Continue searching

Algorithms on long paths and cycles in graphs

Dissertation
Author: Shuxin Nie
Abstract:
Finding a longest path or cycle in a graph is a basic problem in graph theory. This problem is NP-hard since it has the Hamiltonian path or cycle problem as a special case. The thesis is working on finding 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 find 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 find 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 find a cycle of length ≥ log n under appropriate complexity assumption. The previously known technique of color coding can find cycles of length exactly k, for any k ≤ log n, in poly time. However finding a cycle of length ≥ k is a much harder problem, e.g. it might require finding a Hamiltonian cycle. For undirected graphs, this thesis gives an algorithm that can find a cycle of superpolylogarithmic length in polynomial time. ie, length exp[Special characters omitted.] Q , for [cursive l] the length of a longest cycle. It not only simplifies Gabow's algorithm in a previous work but also improves his result. As an indicator of the difficulty on this problem recall that the best hardness result proved to date is that an undirected cycle of length [Special characters omitted.] n/2O log 1-3 n cannot be found in polynomial time, if N P [Special characters omitted.] DT I M E [Special characters omitted.] 2O log 1/3 n , an assumption far stronger than P ≠ NP. In the thesis we also extend the algorithms from finding simple cycles to finding edge simple closed walks, which is a field 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 find edge simple closed walks. We also proved the same hardness results for both problems.

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 final copy of this thesis has been examined by the signatories,and we find 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 finding 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 find 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 find 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 find a cycle of length ≥ log n under appropriate complexity assumption.The previously known technique of color coding can find cycles of length exactly k,for any k ≤ log n,in poly time.However finding a cycle of length ≥ k is a much harder problem,e.g.it might require finding a Hamiltonian cycle. For undirected graphs,this thesis gives an algorithm that can find a cycle of superpolylogarithmic length in polynomial time.ie,length exp(Θ( √ ℓ)),for ℓ the length of a longest cycle.It not only simplifies Gabow’s algorithm in a previous work but also improves his result.As an indicator of the difficulty 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 finding simple cycles to finding

iv e dge simple closed walks,which is a field 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 find 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 Different 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-first 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 first 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 first 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 figure represents an ES-block....................................34 4.5 Finding a component cover on X:In this figure 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 figure 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 first 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 difficult 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 find 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 find 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 find a vw-path of length ≥ log n/log log n.

2 F or undirected graphs,our algorithm can find 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 finding cycles can be used to find circuits,although the approximation ratios may change for the undirected case. 1.1 Previous Results Monien [14] was the first to work on fixed parameter algorithms and he gave an algorithm that can find 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 efficiently. Fellows and Langston [16] introduced the use of depth-first search in this field. They developed algorithms to find undirected cycles of length ≥ k using Robertson- Seymour theorem [9],which classifies 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 find 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 find a “colorful” path (every vertex on the path has a different color) by dynamic programming.Color coding can be used to find paths,cycles and other subgraphs (for example,paths with fixed endpoints) of guaranteed size.This algorithm works on both directed and undirected graphs.It can find a path of length ≥ log n in polynomial time.This is still the best result for directed graphs.For cycles,color coding finds 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 find 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 find 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 find 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 efficiently,for b = 2(∆−1) 2 +1.

4 I t’s simple to see that the Directed problems are more difficult 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-first search.Bodlaender’s algorithm[6] does not apply to directed graphs since the depth-first search on directed graphs produces different types of nontree edges.Gabow and Nie studied the structure of directed cycles and make use of the depth-first search tree to find 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 find 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 find 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:finding an undirected cycle through specific number of given elements (vertices and edges).Robertson and Seymour [38] showed that more generally,the fixed 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 find a cycle through three given vertices with no large hidden constants.(See also [45].) We have find polynomial algorithms to find 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 first present our algorithm of finding 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-first 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 find 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 find 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 finding cycles,we wish that those algorithms can also be used for finding circuits.We first 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 finding a longest cycle is equivalent to the problem of finding 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 find a circuit of length ≥ ∆,for ∆ the maximum degree of the graph for circuits.Combining the reduction and this algorithm,we get an algorithm for finding circuits in undirected graphs. But the above algorithm for finding circuits won’t work for finding 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 find an S-circuit of length exp(Ω( √ log ℓ)) in polynomial time,for ℓ the length of a longest S-circuit.When S = ∅, we find a long circuit;when S contains every vertex of the given graph,we find 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 briefly 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 first 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 defined 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 first 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 find a long directed cycle and the other is to find a long directed vw-path for v,w two vertices of the graph.Note that the second algorithm is a generalized version of the first algorithm,since we can find a long cycle by searching for a vw-path for every edge (w,v) in the graph. For both problems,our algorithms may find a much longer,even Hamiltonian, path or cycle.Observe this cannot be done by color coding:it can only find 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 first 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 find 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-first search tree of G.We define 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 defined 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 satisfies lowpoint(v) < v. Then,we can define 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 defined 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 first 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 qualifies as x the choice of x is arbitrary.) Let (v,w) be a nontree edge.Let a be the first vertex in L w that is an ancestor of v.Define 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 finding 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 efficient to compute the lowpoint cycles,we first 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 definition 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 find 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 first 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-first 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

Full document contains 131 pages
Abstract: Finding a longest path or cycle in a graph is a basic problem in graph theory. This problem is NP-hard since it has the Hamiltonian path or cycle problem as a special case. The thesis is working on finding 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 find 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 find 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 find a cycle of length ≥ log n under appropriate complexity assumption. The previously known technique of color coding can find cycles of length exactly k, for any k ≤ log n, in poly time. However finding a cycle of length ≥ k is a much harder problem, e.g. it might require finding a Hamiltonian cycle. For undirected graphs, this thesis gives an algorithm that can find a cycle of superpolylogarithmic length in polynomial time. ie, length exp[Special characters omitted.] Q , for [cursive l] the length of a longest cycle. It not only simplifies Gabow's algorithm in a previous work but also improves his result. As an indicator of the difficulty on this problem recall that the best hardness result proved to date is that an undirected cycle of length [Special characters omitted.] n/2O log 1-3 n cannot be found in polynomial time, if N P [Special characters omitted.] DT I M E [Special characters omitted.] 2O log 1/3 n , an assumption far stronger than P ≠ NP. In the thesis we also extend the algorithms from finding simple cycles to finding edge simple closed walks, which is a field 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 find edge simple closed walks. We also proved the same hardness results for both problems.