home · mobile · calendar · defenses · 2007-2008 · 

Thesis Defense - Nie

Algorithms on Long Paths and Cycles in Graphs
Shuxin Nie
Computer Science PhD Candidate

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. In directed graphs, the 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. 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, the thesis gives an algorithm that can find a cycle of superpolylogarithmic length in polynomial time. It not only simplifies a previous result of Gabow's algorithm but also improves his result.

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. The thesis also proved the same hardness results for both problems.

Committee: Harold (Hal) Gabow, Professor (Chair)
Richard Byrd, Professor
Debra Goldberg, Assistant Professor
Michael Main, Associate Professor
San Skulrattanakulchai, Gustavus Adolphus College
Department of Computer Science
University of Colorado Boulder
Boulder, CO 80309-0430 USA
May 5, 2012 (14:20)