Course Outline

We discuss fundamental graph algorithms and FPT (fixed-parameter tractable) algorithms. We focus on creative ideas and useful techniques in designing graph algorithms, for instance, a general greedy paradigm for minimum spanning trees, Johnson's reweighting technique for shortest paths, and interesting applications of network flows.

For about 2/3 of the course, we will discuss FPT algorithms for solving NP-hard graph problems. An FPT algorithm confines the exponential time of an algorithm for an NP-hard problem to some part of the input, called parameter k, and therefore solves the problem efficiently for small k, which can be very useful in practice. We will discuss various tools for designing FPT algorithms: from basic tools (bounded search tree, and kernelization) to novel tools (iterative compression of Reed, Smith and Vetta, colour coding of Alon, Yuster and Zwick, and random separation of Cai, Chan and Chan). We will also discuss the theory for fixed-parameter intractability, which is akin to the theory of NP-completeness.

Prerequisite: CSCI2110 and CSCI3160 or their equivalents.

Course Information

Lecture: M10:30-1:15 (ERB 706) by Prof. CAI Leizhen

Grading scheme: Homework (40%), Quiz (10%) and Course Project (50%)

References

1. R.G. Downey and M.R. Fellows, Parameterized Complexity, Springer-Verlag, 1999.
2. R. Niedermeier, Invitation to Fixed-Parameter Algorithms, Oxford Press, 2006.
3. J. Kleinberg and E. Tardos, Algorithm Design, Pearson Education, 2006.
4. T. Cormen, C. Leiserson, R. Rivest, and C. Stein, Introduction to Algorithms, MIT Press, 2001.
5. Selected journal and conference papers.