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


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 wellversed 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.
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 12; wikipedia is useful source for basic graph theory concepts 
L2  Feb 5, Th  Halls Thm, Bipartite matching, nonbipartite matching applications (N)  Nice
slides
on Hall's theorem; bipartite matching and applications 5coloring planar graphs (pdf; from page 10); 
L3  Feb 11, We  Maxflow; circulation and applications;  Slides on maxflow bascis and maxflowmincut theorem 
L4  Feb 12, Th  Advanced Applications of maxflow; (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 HarPeled's proof of planar separator thm. Old lecture notes (pdf) 
L6  Mar 5, Th  Planar Duality and application to exact algorithm for planar maxcut (N)  Feige's notes on
planar maxcut (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ősRé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 2coloring) 
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 2SAT, 3COL (J)  Lecture notes 
E2  Apr 01, We  Problem session (N)  
Apr 02, Th  Midterm  (Solutions) (pdf)  
L12  Apr 22, We  Probabilistic arguments: Karger's mincut algorithm, SchwartzZippel (J)  Lecture notes Books on randomised algorithms: Motwani & Raghavan, Mitzenmacher & Upfal 
E3  Apr 23, Th  Midterm (resit) 

L13  Apr 29, We  BenczúrKarger 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 inclusionexclusion + applications (pdf)
; Survey on exact algorithms (pdf) ; Paper of Ryan Williams on max3sat using triangle finding (pdf) 
L16  May 7, Th  InclusionExclusion; FPT (N)  Midterm resit solutions (pdf) ; Homework 3 (pdf) 
L17  May 13, We 
Color Coding, ETH; No FPT for independent sets  Slides on color coding for kpath (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:0012:00  Older final exams for practice 2012,
2013, 2014
(warning: some of the course content was different than what we covered this year) 