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

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 previous editions of the course (2012, 2013


Administrative Information

Lectures:  Tuesdays  (Hours 5 and 6, i.e. 13:45 - 15:30)
                   Location:  Auditorium 10  from Apr 22 -  Jun 17

                   Thursdays  (Hours 5 and 6, i.e. 13:45 - 15:30)  
                   Location: Auditorium 7

(The course will consist of lectures and several exercise sessions. See detailed schedule below)

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


Study material:

Tentative Topic List:

Note: The above list is tentative.



Homeworks:
(see guidelines above)

Homework 1  (due Feb 28,2014)
Homework 2  (due Apr 22, 2014)
Homework 3  (due June 17, 2014)

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, co-NP, examples Exercise 1 (pdf);  5-coloring planar graphs (pdf; from page 10); wikipedia is useful source for basic graph theory concepts
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 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 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 ( 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.
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 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
L10
May 1, Th Coloring dense 3-colorable graphs, randomized 2-SAT 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; 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 Gerhard Woeginger

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
Final Exam