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


Instructor:
Nikhil Bansal 
MF 4.103.
Ph: 040 247 2299. Email: n dot
bansal at tue dot nl
Grading Policy: The final grade will be based on a written exam (40%), homeworks (40%), scribe notes (20%). You can work on homeworks in groups of up to three persons.
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.
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.
Remarks: Unlike last year, we will focus on the design of exact algorithms. Techniques for approximation algorithm design will be studied in the related course Approximation Algorithms (2WO07).
Template for Scribe notes (from last year)Study material:
Tentative Topic List:
Note: The above list is tentative.
Homework Exercises:
(you can work in groups of up to three students)
Lectures:
(Tentative Plan, will
be updated as the course proceeds)
Lecture  Date/Location  Topic  Reading Material and Scribe Notes 
1  Feb 5, Tu,  Graph Theory: Introduction and Overview  
2  Feb 7  Introduction. NP, CoNP and examples 
Scribe notes 2 (pdf) 
3  Feb 19, Tu,  Bipartite matching, maxflow and applications 
Hw1 available; some reading material (see next lecture) Scribe notes 3 (pdf) 
4  Feb 26, Tu  Maxflow and applications continued 
Hastad's notes on maxflow and bipartite matching (Ch. 12 and 13). Nice slides on applications. Scribe notes 4 ( pdf) 
5  Feb 28 Th  Planarity testing and planar separator theorem 
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. Scribe notes 5 (pdf) 
6  Mar 5, Tu,  Planar Duality and application to exact algorithm for planar maxcut  Feige's notes on
planar maxcut (first page). Prop. 1.9.1 and 1.9.2 in Diestel (on cut
& cycle space). Excellent optional
reading:
Has proof of Koebe's theorem and tons of other great stuff! Scribe notes 6 (pdf ) 
7  Mar 7, Th  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 7 ( pdf ) 
Mar 12 and 14, Tu & Th  no class  
8  Mar 19, Tu  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 8 ( pdf ) 
Mar 21, Th  no class (SDP day at CWI)  
9  Mar 26, Tu  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 ) 
10  Mar 28, Th  Topological Arguments: Chromatic Number of Kneser graphs. HamSandwich Theorem, necklace splitting  Nice notes on chromatic number of
Kneser graphs.
Wikipedia on HamSandwich
theorem. Scribe notes from last year (pdf ) 
Apr 2, Tu  no class (blame Twente)  
Apr 4, Th  no class (blame Twente)  
11  Apr 23, Tu  Nonbipartite matching  Jan Vondrak's notes on nonbipartite matching. Scribe 11 ( pdf ) 
12  Apr 25, Th  Finish nonbipartite matching. Extremal graph theory. Turan's theorem, Ramsey upper bound. 3colorable graphs  Scribe 12 ( pdf ) 
Apr 30 and May 2  no class  
13  May 7, Tu  Coloring dense 3colorable graphs, randomized 2SAT algorithm, Chernoff bound statement.  Scribe 13 (pdf) 
May 9, Th  TU/e closed  
14  May 14, Tu  Chernoff Bound proof and applications. Edge Disjoint Paths.  Scribe 14 ( pdf ) 
15  May 16, Th  Discrepancy. Discussion of homework 2  Scribe 15 ( pdf ) 
May 21 and 23  no class  
16  May 28, Tu  Graph Sparsification  Notes of Nick
Harvey. Scribe 16 (pdf) 
17  May 30, Th  Exact Algorithms, branching, fixed parameter tractability, noexistence of FPT for independent set  Nice survey on proving lower bounds assuming ETH. Scribe (pdf) 
Jun 4, Tu  no class  
18  Jun 6, Th  Color coding, algorithms on trees  
Jun 11, Tu  no class: Speech 2015 event  
19  Jun 13, Th  Color coding: subexponential algorithm for feedback arc set in tournaments (FAST). Discussion of homework 3.  The Fast FAST paper. Scribe 19 (pdf) 
20  June 20, Th  Final Exam 