Graphs & Algorithms: Advanced Topics (251-1409-00 L) HS09
Time & Place
- Lecture: Wednesday 10:15-12:00, CAB G56
-
Dan Hefetz, CAB H32.1, Tel: 044 632 70 53, lastname@inf.ethz.ch . Uli Wagner, CAB G33.2, Tel: 044 632 73 39, firstname@inf.ethz.ch . - Exercise: Thursday 11:15-12:00, CHN D42
-
Heidi Gebauer, CAB G31.2, Tel: 044 632 28 66, lastname@inf.ethz.ch .
Course Description
This course covers a selection of topics from graph theory and the theory of graph algorithms. Possible topics include
- planar graphs (Kuratowski's Theorem, Lipton-Tarjan separators)
- treewidth
- network flows ("push/relabel" method of Goldberg and Tarjan)
- matchings in general graphs (Tutte-Berge Theorem; algebraic algorithms)
- equitable coloring (Hajnal-Szemerédi Theorem, algorithm of Kostocka and Kierstead)
- list coloring (Galvin's Theorem, stable matching algorithm)
- extremal graph theory (Erdős-Stone Theorem, Szemerédi's Regularity Lemma)
- property testing
Prerequisites
You should be familiar with the material covered in "Graphs & Algorithms" from FS09. The topics discussed there include
- Trees (minimum spanning trees, existence of (1,.5)-separator, Cayley's Theorem)
- Block decomposition, Menger's Theorem
- Matchings in bipartite graphs (Hall's Theorem, König's Theorem, Algorithm of Hopcroft and Karp, Hungarian method)
- Hamilton Cycles (Dirac's Theorem, Euclidean TSP (2^n-alg, 2-approx))
- Planar graphs (Euler's Formula, 5-coloring theorem, sketch of the 4-coloring proof, planarity testing in n^2 time)
- Coloring (Greedy coloring, Brook's Theorem, Mycielski's Construction, Erdős' Construction, Vizing's Theorem, Dirac/Hadwiger)
- Extremal graph theory (Ramsey's Theorem, Turán's Theorem)
Exercises
In every lecture we provide you with an exercise sheet. Some of the exercises are to be discussed and solved outside the class. This counts as a part of the extra hour of independent work (A).Others - usually one per week - you solve in written form and return the solutions at the beginning of the subsequent lecture. Your solutions will be thoroughly commented and graded, but they do not count towards your final grade. The motivation to work on the homework stems from your interest in the topic (and possibly also the desire to succeed on the exam :-)
The exercise session is devoted to the presentation and discussion of solutions.
Exam
There will be an oral exam of 20 minutes at the end of semester. Your grade is purely based on this exam. However, one of the questions given to you during the exam will be to solve one of the exercises or homeworks posed throughout the semester.You are expected to learn proofs discussed in the lecture, should be able to explain their basic ideas and reproduce more details on demand. You should also be able to give a short presentation on any topic treated throughout the course.
Roughly half an hour before your exam you get to know the exercise to be solved and one topic that you will be questioned about in particular, that is, you have 30 minutes preparation time. For this preparation, paper and pencil will be provided. You may not use any other material, like books or notes.
Literature
- D. B. West: Introduction to Graph Theory, Prentice Hall, 2001.
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein: Introduction to Algorithms, 2nd edition, MIT Press and McGraw-Hill, 2001.
- A. Steger, Skript zur Vorlesung "Graphenalgorithmen", 2005. (in German)
- H. A. Kierstead and A. V. Kostochka, A Short Proof of the Hajnal-Szemerédi Theorem on Equitable Coloring, manuscript, 2006.
- R. Diestel Graph Theory, Springer-Verlag, Heidelberg. (freely available electronic edition in English and German)
- E. Fischer, The art of uninformed decisions: A primer to property testing, The Computational Complexity Column of The Bulletin of the European Association for Theoretical Computer Science 75 (2001), 97-126. Also in: Current Trends in Theoretical Computer Science: The Challenge of the New Century (G. Paun, G. Rozenberg and A. Salomaa eds.), World Scientific Publishing (2004), Vol. I 229-264.
- J. Matousek, Chapter 5 in Lecture Notes to the Core Subject course "Algorithms, Probability, and Computing", Computer Science Department, ETH Zurich, September 2007.
- N. J. A. Harvey, Algebraic Algorithms for Matching and Matroid Problems, SIAM Journal on Computing, to appear.
