2WO08: Graphs and Algorithms (Semester B, 2014)
Nikhil Bansal -
Ph: 040 247 2299. Email: n dot bansal at tue dot nl
Ruben van der Zwaan Email:
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 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).
Tentative Topic List:
Note: The above list is tentative.
(Tentative Plan, will be updated as the course proceeds)
|L1||Feb 4, Tu,||Introduction, basic graph theory, NP, co-NP, examples||Exercise 1 (pdf); 5-coloring
planar graphs (pdf;
from page 10); wikipedia is useful source for basic graph theory
|L2||Feb 6, Th||Bipartite matching, max-flow and applications||Hoffman's circulation theorem (pdf, sections 1.1 and 1.2); notes on max-flow; notes on bipartite matching; nice slides on applications of max-flow, Konig-Egervary,...|
|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 Har-Peled's proof of planar separator thm. Notes for the lecture (pdf)|
|L4||Feb 25, Th||Planar Duality and application to exact algorithm for planar max-cut||Feige's notes on
planar max-cut (first page). Excellent optional
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.
Tao's blog on crossing
Notes on graps with large girth,chromatic number.
Scribe notes (pdf)
|L6||Mar 13, Th||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 ( pdf) (ignore the part on super-concentrators)
|E4||Mar 18, Tu||Exercise|
|L7||Mar 20, Th||Algorithmic
uses of Probability: Karger's min-cut,
Schwartz Zippel Lemma and matching.
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
|Apr 24, Th||Mid-term 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|
||May 1, Th||Coloring dense 3-colorable graphs,
||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; inclusion-exclusion method; dynamic programing; braching; algorithms on trees||Nice slides
on inclusion-exclusion by Lukasz Kowalik. Many things we dicussed can
be found in this survey by
|L14||Jun 5, Th
||fixed parameter tractability, no-existence 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:00-12:00