2WO08: Graphs and Algorithms (Semester B, 2015)

Nikhil Bansal and Jorn van der Pol



Course Summary

       This course will have multiple objectives. First, we will study several basic concepts in graph theory, getting a broad introduction to the area and the different techniques used. Next, we will study the algorithmic aspects of various graph theoretic problems. The focus will be on understanding how structural results in graph theory are useful in designing algorithms for various fundamental  and practical optimization problems.

For more details, see previous editions of the course (2012, 2013, 2014


Administrative Information

Lectures:  Wednesdays  (Hours 1 and 2, i.e. 8:45 - 10:30)
                   Location:  Flux 1.05

                   Thursdays  (Hours 5 and 6, i.e. 13:45 - 15:30)  
                   Location: Flux 1.06 till April 2, and Helix Oost 3.91  from Apr 23 - June 18

(The course will consist of lectures and several exercise sessions. See detailed schedule below)

Exam: July 1;  Time 9:00-12:00 Location: TBD     Interim: August 12, 9:00-12:00

Instructors:  Nikhil Bansal -   MF 4.95
                    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).


Study material:

Tentative Topic List:

Note: The above list is tentative.



Homeworks:
(see guidelines above)

Lectures:

(Tentative Plan,  will be updated as the course proceeds)

Lecture Date/Location Topic                                           Reading Material                                                
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 slides 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 class

L5 Mar 4, We  Planarity testing and planar separator theorem  (N) Wikipedia on planar graph basics four color theorem , planar separator theorem. 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 reading:  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 arguments: Erdős-Rényi random graph,
Clique size in G(n,1/2) via second moment method (J)
Lecture notes
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 applications (J)
Lecture notes
E1 Mar 25, We Problem session
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
no class
L18 Jun 3, We Treediwdth  + Feedback arc set in tournaments
The 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,  2013, 2014  (warning: some of the course content was different
than what we covered this year)