## Course Summary

#### (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:

• #### There is no particular textbook for the course. The relevant reading material will be provided during the course.

Tentative Topic List:

• Concepts from Graph Theory
• Matchings: Bipartite and general graphs, related min-max theorems. Applications. Chinese Postman Problem, TSP.
• Planarity:  Duality, finding max cut in planar graphs, planarity testing algorithm, planar separator theorem and applications.
• Flows: Max-flow Min-cut, min-cost circulations and their various applications, connectivity results.
• Structural Graph Theory:  Treewidth, Graph Minors, Applications
• Operations on Graphs:  Graph Products, Line Graphs. Application to independent set hardness.
• Probabilistic Methods: Various graph constructions, Expanders and their applications, Karger's min-cut, polynomial identity testing.
• Extremal graph theory: Basic results
• Algebraic Methods: Graph Spectra and expansion, Determinants, Permanents, Pfaffians.
• Algorithmic Concepts:
• Power of min-max relations: NP and co-NP problems.
• LP Duality: Understanding Bipartite Matching, Flow, Shortest Paths via LP duality.
• Simple LP rounding techniques
• Treewidth and algorithmic applications: Baker's technique. Bidimensionality
• Exact Algorithms: Dynamic programming, color coding, algebraic techniques, kernelization,
• Counting techniques: Mobius inversion, subset convolution
• Randomized Graph Algorithms: Graph Sparsification.

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)

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