Graphs & Algorithms: Advanced Topics (251-1409-00 V) HS07
Time & Place
- Lecture: Wednesday 10:15-12:00, CAB G56
-
Tibor Szabó, CAB G31.2, Tel: 044 632 08 58, lastname@inf.ethz.ch . - Exercise: Wednesday 15:00-17:00, CAB H57
-
Michael Hoffmann, CAB G33.1, Tel: 044 632 73 90, 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 SS07. 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)
Outlook: In SS08 there will be a seminar "Advanced Topics in Discrete Mathematics: Graphs" (together with Angelika Steger).
Exercises
In every lecture we provide you with an exercise sheet. Some of the exercises are to be discussed and solved in small groups during the first hour of the weekly exercise sessions.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 second hour of the exercise sessions is devoted to the presentation and discussion of solutions.
Exam
There will be an oral exam of 30 minutes during the examination period. 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.
