Location:
Hans Freudenthal Gebouw (Mathematical Building), Room 611AB, Budapestlaan, de Uithof, Utrecht.

Time:
Monday 11.00 - 12.45, November 19-December 17 and January 21-February 18.

Course material:
The course will be based on parts of the Lecture Notes: A Course on Combinatorial Optimization by A. Schrijver (abbreviated below as [LNAS]).
Additional material which will be made available through the course (links for download will be posted below).

Examination:
Take home problems will be distributed on a weekly basis and will be posted below.

The exercises can be handed in after the end of the course.
The deadline to send the exercises is April 1st.

Please mail a print or email them (pdf file, no doc file) at the following address:
Monique Laurent, CWI, Science Park 123, 1098 XG Amsterdam
M.Laurent at cwi dot nl

Weakly assignments:

Lecture about part of Chapter 6 and of Chapter 7.1 in [LNAS]: basic facts about complexity, introducing basic graph parameters (stable sets, cliques, coloring, vertex and edge covers) and some facts on their complexity.

The exercises can be found here. We will discuss the Strong Perfect Graph Theorem next week as well as the notion of graph minors, so you may want to postpone working on Exercises 3, 4 till next week.

Monday November 26:

Lecture about Chapters 7.1, 7.2, 7.3 in [LNAS]: vertex and edge coloring of graphs; Dilworth theorem in partially ordered sets.

Exercises 7.9(ii), 7.12, 7.19, 7.22.

Monday December 3:

Lecture about Chapter 7.4 (perfect graphs) and part of Chapter 7.5 in [LNAS]: definition of chordal graphs, existence of simplicial vertices, perfect elimination orderings of chordal graphs and their use to find maximum stable sets, maximum cliques, and minimum colorings in polynomial time.

Exercises 7.27 and 7.32 in [LNAS] and the following two exercises:

Exercise A: Assume that G1 and G2 are two perfect graphs, with disjoint sets of vertices. Build the new graph G, obtained by taking the union of G1 and G2, and adding all possible edges between nodes of G1 and nodes of G2. Show that G is perfect.

Exercise B: Give a class of perfect graphs having exponentially many maximal stable sets and exponentially many maximal cliques (in terms of the number of nodes).

Monday December 10:

Lecture about Chapter 7.5 in [LNAS]: tree representations of chordal graphs, including clique-tree representations and the link to tree-width for general graphs. A brief start about Chapter 3.2.1 in the SDO Lecture Notes, abbreviated below as [SDO].
Please read Chapter 1 of [SDO] (preliminaries about positive semidefinite matrices) before the next lecture.
If you are interested to read more about chordal graphs (and the related concepts of partial k-trees and tree-width of graphs) you may look at the following short survey by Heggernes.

Exercises 7.28 and 7.29 in [LNAS].
Hints for Exercise 7.29 can be found here.

Monday December 17:

Lecture about Chapters 3.2, 1 and 2.1 in [SDO].
Please read the rest of Chapter 2 before the next lecture on Monday 21/01/2019.

Exercises 1.1, 1.2, 2.2, 2.3 in [SDO].

Monday January 21:

Lecture about Chapters 3.3 and 3.4 in [SDO] (theta number, polynomial time algorithm for maximum stable set and minimum coloring in perfect graphs, other formulations of theta number).

Exercises 3.1, 3.3 in [SDO].

Monday January 28:

Lecture about Chapters 3.5,3.6,3.7 (theta body, theta number of vertex-transitive graphs, Shannon capacity).

Exercise 3.2 in [SDO] and this exercise.

Monday February 4:

Lecture about Sections 4.1 and 4.2: Max-Cut, SDP relaxation and Goemans-Williamson approximation algorithm.

Exercises 4.3, 4.4 and 4.5 in [SDO].

Monday February 11:

Lecture about Chapters 4.3 and 4.4: Extension to max k-cut, max bisection, max 2SAT and quadratic programming (Nesterov approximation ratio).

Exercises 4.6 and 4.7 in [SDO].
Note: In Exercise 4.6, no need to assume that the weights on the edges are non-negative.

Monday February 18: No lecture.