LNMB PhD Course Networks and Semidefinite Programming - 2nd Trimester in 2022-2023

This course belongs to the LNMB program of PhD Courses.

Location
This course is given onsite at Utrecht Campus Science Park. The lectures will also be streamed and be accessible online. Details about the lecture rooms and online facilities are sent via LNMB after registration to the course.

Time:
Monday 11.00 - 12.45, November 21 - December 19 2022 and January 30 - February 27 2023.

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

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]). A version with a few typos corrected has been uploaded at the shared surf drive folder.

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

Rules:
- You may work in 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 mail a print or email them (pdf file, no doc file) at the following address:
Sven Polak, CWI Science Park 123, 1098 XG Amsterdam, Sven.Polak@cwi.nl (with cc to M.Laurent@cwi.nl)
- The deadline to send the solutions is March 17 2023.

Program of the course and weekly assignments:

Monday 21 November [only onsite, not streamed]
Room 061 in Buys Ballot building.

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.6 in [LNAS], Exercises A & B as posted at the shared surfdrive folder. (You may want to work on Exercise B after the next lecture.)

Monday 28 November
Room 061 in Buys Ballot building.

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

Homework Exercises: posted at the shared surfdrive folder.

Monday 5 December
Lecture in Minaert building, room 2.02.

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.12, 7.22 (in [LNAS]) and Exercises A, B below.
Hint: in Exercise 7.12 you may use Konig's edge-coloring theorem (which applies for graphs with multiple edges).
You may find the definition of transversals in Exercise 3.4 of [LNAS].

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 12 December
Lecture in Minaert building, room 2.07

Lecture about Chapter 7.5 in [LNAS]: chordal graphs, simplicial nodes and perfect elimination orderings, efficient algorithms for cliques, stable sets and coloring. Tree representations of chordal graphs were briefly introduced and will be further discussed in 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.

Homework exercises: Exercises 7.30 and 7.32 in [LNAS].

Monday 19 December [only onsite, not streamed]
Lecture in Buys Ballot building, room 079

Follow-up on chordal graphs: tree representations, clique-tree representations, and short introduction to tree-width for general graphs.
Lecture about Section 3.2.1 and Section 3.3.1 in the Lecture Notes [NSP]: LP approach to maximum stable sets and minimum coloring, fractional stable sets and coloring, introducing Lovasz theta number.

Before the next lecture on Monday 30 January, please read Chapter 1 in [NSP] containing preliminaries about positive semidefinite matrices.

Homework Exercises: Exercise 1.1 in [NSP]. (Hint: think of using the Schur complement operation)

Exercise A: Consider the matrix M with entries M(i,j)= 1/(i+j) for i,j=1,..,n. Show that M is positive semidefinite. (Hint: Given a nonnegative integer k, if you integrate the function x--> x^k over the interval [0,1], what value do you get?)

Exercise B: Consider the complete graph G on n nodes, with edge weights w(i,j) for its` edges (i,j), and consider the associated Laplacian matrix L. That is, L is the matrix of size n, with off-diagonal entries L(i,j)=L(j,i)=-w(i,j) for distinct i,j, and whose diagonal entry L(i,i) is defined as the sum of the weights w(i,j) over all pairs (i,j) with j distinct from i. Show that if all edge weights are nonnegative then the Laplacian matrix L is positive semidefinite.

Monday 30 January
Lecture: Buys Ballot building, room 061

Lecture about Chapter 2 (primal and dual SDP programs, weak duality, strong duality under strict feasibility, efficient algorithm), Chapter 3.3 (theta number), Chapter 4 (dual formulation of theta number and link to fractional coloring) in [NSP].

Exercises 2.3 and 3.1 in [NSP] and Exercise A posted at the shared surfdrive folder.

Monday 6 February
Lecture: Buys Ballot building, room 023

The class is cancelled because of bus strikes in Utrecht.

Monday 13 February
Lecture: Minaert building, room 2.01

Lecture about Chapters 3.4, 3.5, 3.6 and 3.7 in [NSP] (theta body, dual form ulation for theta number, lifted formulations for theta, bounding Shannon capacity, theta number for vertex transitive graphs).

Exercise 3.2 in [NSP] and Exercise B posted at the shared surfdrive folder.

Monday 20 February [only onsite, not streamed]
Lecture: Buys Ballot building, room 161

Lecture about Sections 4.1 and 4.2 in [NSP]: Max-cut, LP relaxation, SDP relaxation, and Goemans-Williamson approximation algorithm.

Exercises 4.4 and 4.5 in [NSP].

Monday 27 February
Lecture: Buys Ballot building, room 023

Lecture about Chapters 4.3 and 4.4: Extension to max k-cut, max 2SAT and quadratic programming (Nesterov approximation ratio). We did not have time to cover the extension to max bisection, please read about it in Section 4.3.1.

Exercises 4.6 and 4.7 in [SDO].