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

Nikhil Bansal

Course Summary

       This course will have multiple objectives. First, we will study several basic concepts in graph theory, getting a broad introduction to the area and the different techniques used. Next, we will study the algorithmic aspects of various graph theoretic problems. The focus will be on understanding how structural results in graph theory are useful in designing algorithms for various fundamental  and practical optimization problems.

For more details, see the course from last year  (though the topics we cover this year might be somewhat different) 

Administrative Information

Lectures:  Tuesdays  (Hours 7 and 8, i.e. 15:45 - 17:30)
                   Location:  Auditorium 12 until Apr 2     (except in Auditorium 9 on Apr 2) ,  and   Pav J17  from Apr 23 -  Jun 18

                   Thursdays  (Hours 3 and 4, i.e. 10:45 - 12:30)  
                   Location: Potential 9.05  

(We will not have lectures on some days, see detailed schedule below)

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 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)

Study material:

Tentative Topic List:

Note: The above list is tentative.

Homework Exercises:
(you can work in groups of up to three students)

Hw 1  (due 19/3/03) 
Hw 2 (due 24/04/03)
Hw 3 (due 13/06/03)


(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
Wikipedia on planar graph basics four color theorem , planar separator theorem. 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 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 super-concentrators 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 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 Kneser graphs. Wikipedia on Ham-Sandwich 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  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