Graph algorithms (Master 2 ICS, 2023-2024)

I teach 10 hours, and Laurent Beaudou teaches the other 10 hours.

Lecture 1 (October 19)

• Topics: algorithmic complexity, reductions, NP-completeness
• slides

Lecture 2 (October 20)

• Topics: greedy independent set for intervals, greedy coloring for intervals, properties and greedy colorings of chordal graphs
• Source for chordal/triangulated graphs: chapter 4 in the book Algorithmic Graph Theory and Perfect Graphs
  by Martin C. Golumbic
  Elsevier, 2004.

Lecture 3 (October 27)

• Topics: independent set for trees, treewidth, independent set for graphs of bounded treewidth
• source: chapter 7 in Parameterized algorithms
  by Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk and Saket Saurabh
  Springer, 2015.
• slides by Ignasi Sau
• nice tree-decompositions: see slide number 21 of the above presentation

Break between October 27 and November 30

• Exercise sheet

Lecture 4 (November 30)

• Topics: solution of exercises: exercises 1 and 2, nice tree-decompositions

Lecture 5 (December 1)

• Topics: Courcelle's theorem, definition of FPT algorithms, solution of exercises on dominating set