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


Instructor:
Nikhil Bansal 
MF 4.103.
Ph: 040 247 2299. Email: n dot
bansal at tue dot nl
TA:
Ruben van der Zwaan Email:
g.r.j.v.d.zwaan@tue.nl
Prerequisites:
This
is a masters level class and a basic
background in
algorithms and discrete mathematics is expected. Familiarity with some
basic ideas from optimization will be helpful, but is not necessary.
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, Tu,  Introduction, basic graph theory, NP, coNP, examples  Exercise 1 (pdf); 5coloring
planar graphs (pdf;
from page 10); wikipedia is useful source for basic graph theory
concepts 
L2  Feb 6, Th  Bipartite matching, maxflow and applications  Hoffman's circulation theorem (pdf, sections 1.1 and 1.2); notes on maxflow; notes on bipartite matching; nice slides on applications of maxflow, KonigEgervary,... 
E1  Feb 11, Tu  Exercise  
E2  Feb 13, Th  Exercise  
L3  Feb 18, Tu,  Planarity testing and planar separator theorem  Wikipedia on planar graph basics, four color theorem , planar separator theorem. Sariel HarPeled's proof of planar separator thm. Notes for the lecture (pdf) 
L4  Feb 25, Th  Planar Duality and application to exact algorithm for planar maxcut  Feige's notes on
planar maxcut (first page). Excellent optional
reading:
Has proof of Koebe's theorem and tons of other great stuff!
Notes (pdf ) 
E3  Feb 27, Th  Exercise  Exercise 2 (pdf) 
L5  Mar 11, Tu  Probabilistic
arguments: crossing number inequality,
graphs with large girth and chromatic number, tournaments with no winners. 
Terry
Tao's blog on crossing
number inequaity. Notes on graps with large girth,chromatic number. Scribe notes (pdf) 
L6  Mar 13, Th  Expanders:
Application to superconcentrators of O(n) size. Clique size in G(n,1/2) via second moment method. 
See
section 9.2 here for
cliques in random graphs. These notes also have other nice applications. Scribe notes ( pdf) (ignore the part on superconcentrators) 
E4  Mar 18, Tu  Exercise  
L7  Mar 20, Th  Algorithmic
uses of Probability: Karger's mincut, Schwartz Zippel Lemma and matching. 
Schwartz
Zippel on wikipedia (proof and applications) Notes on Karger's mincut algorithm. Scribe notes ( pdf ) (ignore the part on graph products) 
April 1, Tu  midterm exam  Exam (pdf); Solutions (pdf)  
L8  Apr 22, Tu  Problem
solving techniques 
(pdf) 
Apr 24, Th  Midterm resit  
L9  Apr 29, Tu  Extremal graph theory. Turan's theorem, Ramsey upper bound.  Proofs of Mantel's and Turan's theorems (pdf); Ramsey upper bound; nice course on extremal graph theory 
L10 
May 1, Th  Coloring dense 3colorable graphs,
randomized 2SAT
algorithm. 
Exercise 3 (pdf) Old scribe notes (pdf) 
L11  May 13, Tu  Graph products; Chernoff bound; applications  Old scribe notes (pdf) 
L12  May 15, Th  Edge disjoint paths; Power of two choices; Graph Sparsification  Old scribe notes (pdf); Notes of Nick Harvey on sparsification 
L13  May 20, Tu  Exact algorithms; Hamiltonian paths; coloring; inclusionexclusion method; dynamic programing; braching; algorithms on trees  Nice slides
on inclusionexclusion by Lukasz Kowalik. Many things we dicussed can
be found in this survey by
Gerhard Woeginger 
L14  Jun 5, Th 
fixed parameter tractability, noexistence of FPT for independent set; Color coding: simple path  Color
Coding (see section 3 here) Nice survey on proving lower bounds assuming ETH. Scribe (pdf) 
L15  Jun 10, Tu 
Problem Solving Session  
Jul 2, Th, 9:0012:00 
Final Exam 