Location
This course is given onsite at Utrecht Campus Science Park: Room HFG 611, Hans-Freudenthal building, Budapestlaan 6.

Time
Monday 11.00 - 12.45, November 18 - December 16 2024, January 6 2025, and January 20 - February 10 2025

Lecturers
Monique Laurent (CWI, Tilburg University), Sven Polak (Tilburg University)

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]), and on the Lecture Notes: Networks and Semidefinite Programming (abbreviated below as [NSP]).

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

Rules:
- You may work in a group of two students and return a common solution set for the group (but every student is expected to work individually on all exercises).
- Write the solutions preferably in Latex. Handwritten solutions must be written in a careful and well readable manner.
- The solutions can be handed in after the end of the course.
- Please email your solutions (pdf file, no doc file) at Sven.Polak@cwi.nl, M.Laurent@cwi.nl
- The deadline to send the solutions is March 17 2025.

Program of the course and weekly assignments:

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

Homework Exercises: Exercise 7.4 in [LNAS], and Exercises A & B posted here.

Monday 25 November [Sven]

Lecture about Chapters 7.1 and 7.2 in [LNAS]: vertex and edge covers, vertex and edge coloring of graphs.

Homework Exercises: Posted here.

Monday 2 December

Lecture about Chapters 7.3 and 7.4 in [LNAS]: Dilworth theorem, basic facts about perfect graphs, and the perfect graph theorem.

Homework exercises: Exercises 7.19, 7.22 (in [LNAS]) and Exercises A, B below.

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).
Hint: You may want to use the result of Exercise A.

Monday 9 December

Homework exercises:

Monday 16 December

Homework Exercises:

Monday 6 January

Homework Exercises:

Monday 20 January

Homework Exercises:

Monday 27 January

Homework Exercises:

Monday 3 February: no class

Monday 10 February

Homework Exercises: