2WO08: Graphs and Algorithms (Semester B, 2013)
Nikhil Bansal -
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.
is a masters level class and a basic
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 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.
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)
Tentative Topic List:
Note: The above list is tentative.
(you can work in groups of up to three students)
(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, Co-NP and examples
||Scribe notes 2 (pdf)
|3||Feb 19, Tu,||Bipartite matching, max-flow and applications
|| Hw1 available; some reading material (see next lecture)
Scribe notes 3 (pdf)
|4||Feb 26, Tu||Max-flow and applications continued
||Hastad's notes on max-flow 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
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.
Scribe notes 5 (pdf)
|6||Mar 5, Tu,||Planar Duality and application to exact algorithm for planar max-cut||Feige's notes on
planar max-cut (first page). Prop. 1.9.1 and 1.9.2 in Diestel (on cut
& cycle space). Excellent optional
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
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 super-concentrators of O(n) size.
Clique size in G(n,1/2) via second moment method.
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 min-cut, 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. Ham-Sandwich Theorem, necklace splitting||Nice notes on chromatic number of
Wikipedia on Ham-Sandwich
Scribe notes from last year (pdf )
|Apr 2, Tu||no class (blame Twente)|
|Apr 4, Th||no class (blame Twente)|
|11||Apr 23, Tu||Non-bipartite matching||
Jan Vondrak's notes on non-bipartite matching. Scribe 11 ( pdf )
|12||Apr 25, Th||Finish non-bipartite matching. Extremal graph theory. Turan's theorem, Ramsey upper bound. 3-colorable graphs||Scribe 12 ( pdf )
|Apr 30 and May 2||no class|
|13||May 7, Tu||Coloring dense 3-colorable graphs, randomized 2-SAT 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, no-existence 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|