LNMB PhD Course Networks and Semidefinite Programming - Fall 2020

This course belongs to the LNMB program of PhD Courses.

This course is given online. Details about the online connection are sent via LNMB after registration to the course.

Monday 13.00 - 14.45, September 7 - November 9 2020.
No class on Monday 21 September.

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

Take home problems will be distributed on a weekly basis and will be posted below.
- You may work in group of 2 or 3 and return a common solution set for the group (but please work individually on all exercises).
- Write the solutions preferably in Latex.
- 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:
Monique Laurent, CWI, Science Park 123, 1098 XG Amsterdam
M.Laurent at cwi dot nl
- The deadline to send the solutions is December 14 2020.

Program of the course and weekly assignments:

Monday September 7

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.

Exercise: The goal is to give a polynomial-time reduction from the vertex-coloring problem to the stable set problem.

Consider a graph G=(V,E) and an integer k. We build a new graph H as the Cartesian product of G and the complete graph K_k on k nodes. Namely, the vertices of H are the pairs (v,i), where v is a vertex of G and i is a vertex of K_k (a number between 1 and k). The edges of H are the pairs {(u,i),(v,i)} where {u,v} is an edge of G and i=1,2,..,k; together with the pairs {(u,i),(u,j)} where u is a vertex of G and i,j are distinct vertices of K_k.
Show that G can be colored with k colours if and only if H has a stable set of size n. (Here n is the number of vertices of G).

Monday 14 September:

Lecture about Chapters 7.1 and 7.2 in [LNAS]: vertex and edge covers, vertex and edge coloring of graphs. Please see the details about edge coloring of bipartite graphs in Chapter 7.2 (and posted class notes).

The exercises can be found here.

Monday September 21: No class

Monday September 28:

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

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 October 5:

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, including clique-tree representations and the link to tree-width for general graphs.

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 October 12:

Lecture about Chapter 3.2 and Chapter 3.3.1 in the Lecture Notes "Networks and Semidefinite Programming" (abbreviated as [NSP]): LP approach to maximum stable sets and minimum coloring, fractional stable sets and coloring, introducing Lovasz theta number.

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 19 October:

Lecture about Chapter 2 (primal and dual SDP programs, weak duality, strong duality under strict feasibility, efficient algorithm) and Chapter 3.3 (finding maximum stable sets in perfect graphs in polynomial time) in [NSP].

Exercises 2.1, 2.2, 2.3 in [NSP].

Monday 26 October:

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

Exercises 3.1, 3.2 in [NSP] and the additionnal exercise that was sent per email on 26/10.

Monday 2 November:

Lecture about Chapters 4.1 and 4.2 in [NSP] (max-cut, LP approach, SDP approach and Goemans-Williamson approximation algorithm).

Exercise 4.1, 4.4, 4.5 in [NSP].

Monday 9 November:

Lecture about Sections 4.3 and 4.4 in [NSP]: Extensions and variations of Goemans-Williamson approximation algorithm for (some instances of) quadratic programming (including Nesterov analysis), max 2-SAT, max k-cut, max bisection.

Exercises 4.6 and 4.7 in [NSP].