2WO08: Graphs and Algorithms (Semester B, 2015)
Nikhil Bansal and Jorn van der Pol
Nikhil Bansal -
Ph: 040 247 2299. Email: n dot bansal at tue dot nl
Jorn van der Pol Email:
j.g.v.d.pol at tue.nl
Prerequisites: This is a masters level class and a basic background in algorithms and discrete mathematics is expected. Above all, the most important prerequisite is mathematical maturity. If you are not familiar with certain topics, you can contact me after the class to extra background reading material.
Goals: At the end of the course, the student should be well-versed in basic concepts of graph theory such as coloring, planarity, independent sets, flows etc. They should understand basic proof techniques in graph theory such as the probabilistic method. They should also be able to use various algorithmic techniques.
Grading Policy: The final grade will be based on homeworks (20%), midterm exam (30%) and final exam (50%).
Homeworks: There will be four homeworks, which can be done in groups of up to 2 people. All homeworks must be written in Tex, and the proofs must be clearly written.
Exercise Sessions: The exercises consists of basic problems which you should master. The exercises sessions are for solving exercises, discussing homework problems (after their due date).
Tentative Topic List:
Note: The above list is tentative.
(Tentative Plan, will be updated as the course proceeds)
|L1||Feb 4, We||Introduction, basic graph theory concepts (N)||Slides for lectures 1-2; wikipedia is useful source for basic graph theory concepts|
|L2||Feb 5, Th||Halls Thm, Bipartite matching, non-bipartite matching applications (N)||Nice
on Hall's theorem; bipartite matching and applications
5-coloring planar graphs (pdf; from page 10);
|L3||Feb 11, We||Max-flow; circulation and applications;||Slides on maxflow bascis and maxflow-mincut theorem|
|L4||Feb 12, Th||Advanced Applications of max-flow; (N)||Applications of maxflow (slides); Homework 1 (pdf)|
|Feb 25, We||no class|
|Feb 26, Th||no
|L5||Mar 4, We||Planarity testing and planar separator theorem (N)||Wikipedia
graph basics, four color theorem , planar
Section 1.5.1 here
has the planarity testing algorithm we discussed.
Sariel Har-Peled's proof of planar separator thm. Old lecture notes (pdf)
|L6||Mar 5, Th||Planar Duality and application to exact algorithm for planar max-cut (N)|| Feige's notes on
planar max-cut (first page). Excellent optional
Has proof of Koebe's theorem and tons of other great stuff! Old lecture notes (pdf )
Slides for lectures 5 and 6 (pdf)
|L7||Mar 11, We||Probabilistic
arguments: First moment method; crossing number inequality,
Ramsey results, tournaments with no winners (J)
|Handout (Probability Basics)
Lecture notes; Terry Tao has an excellent blog post on the crossing number inequality.
Standard book on the probabilistic method: Alon & Spencer
|L8||Mar 12, Th|| Probabilistic
Clique size in G(n,1/2) via second moment method (J)
|L9||Mar 18, We||Probabilistic arguments: alterations, stable sets, Ramsey results (J)||Lecture notes
Some background information on "Property B" (=hypergraph 2-coloring)
|L10||Mar 19, Th||Probabilistic arguments: Chernoff bound and
|E1||Mar 25, We||Problem
||Homework 2 (pdf)|
|L11||Mar 26, Th||Probabilistic arguments: random walks, application to 2-SAT, 3-COL (J)||Lecture notes|
|E2||Apr 01, We||Problem session (N)|
|Apr 02, Th||Mid-term||(Solutions) (pdf)|
|L12||Apr 22, We||Probabilistic arguments: Karger's min-cut algorithm, Schwartz-Zippel (J)||Lecture notes
Books on randomised algorithms: Motwani & Raghavan, Mitzenmacher & Upfal
|E3||Apr 23, Th||Mid-term (resit)
|L13||Apr 29, We||Benczúr-Karger Graph Sparsification (J)|| Lecture notes
A paper by Benczúr & Karger about graph sparsification
|L14||Apr 30, Th||Extremal graph theory. Turan's theorem, Ramsey upper bound. (J)||Proof of Mantel's and Turán's theorems (pdf); Upper
bound on Ramsey numbers
Extremal Combinatorics (Statys Jukna): good book on extremal combinatorics (free draft available on the author's website)
|L15||May 6, We||Exact Algorithms (N); Dynamic Programming||Slides for lectures 15 and 16 (pdf)
; Notes on branching (sections 1 and 2) (pdf)
; Slides on inclusion-exclusion + applications (pdf)
Survey on exact algorithms (pdf) ; Paper of Ryan Williams on max-3-sat using triangle finding (pdf)
|L16||May 7, Th||Inclusion-Exclusion; FPT (N)||Mid-term resit solutions (pdf) ; Homework 3 (pdf)|
|L17||May 13, We
||Color Coding, ETH; No FPT for independent sets||Slides on color coding for k-path (pdf,
see slide 5 and later)
Survey on lower bounds using ETH (pdf). We did Thm 5.1
|E4||May 20, We||Problem session (J)|
|May 21, Th||no class
|May 27, We||no class|
|May 28, Th
|L18||Jun 3, We||Treediwdth + Feedback arc set in tournaments
Feedback arc set in tournaments paper.
Lecture on treewidth
(see definition and section 11.2).
Homeword 4 (pdf)
|E5||Jun 18, Th||Problem session (J)
|Jul 1||Final Exam (location PAV SH1) 9:00-12:00||Older final exams for practice 2012,
(warning: some of the course content was different
than what we covered this year)