Assumed background: Basic notions in graph theory, theory of algorithms, and computational complexity (basic definitions of graph theory, time complexity of algorithms, graph representations, classes P and NP, polynomial reductions, NP-hard problems). It would be helpful, though not necessary, for the student to be acquainted with basic graph optimization problems and algorithms, in particular, with the definitions of the following problems: maximum independent set, minimum vertex cover, minimum spanning tree (MST), maximum matching (MM); with polynomiality of the MST problem and of the MM problem and its variants. Knowing the definitions of interval graphs and of chordal graphs would also be helpful (though not necessary; we will recall the definitions).

Short syllabus:

The 8-hour minicourse will discuss of a selection of topics in structural and algorithmic graph theory, with a particular emphasis on algorithmic and complexity issues.

List of tentative topics covered:

1. Approximation algorithms for graph problems (about 5h).

Basic definitions. Approximation algorithms for the following problems:

- the vertex cover problem (2-approximation; greedy approximation),

- the max cut problem: 2-approximation based on local optimization, randomized 2-approximation,

- the metric TSP (2-approximation; Christofides' algorithm).

(In)approximability of the chromatic number and of the independent set problem in general and in some special cases.

Approximation algorithms for the minimum set cover problem and the minimum submodular cover problem. Applications to graph theoretic problems, in particular to variants of domination.

2. Graph width parameters (about 3h).

Treewidth. Review of the dynamic programming paradigm on trees.

Definition of treewidth and a characterization. Examples of graphs of small treewidth. Nice tree decomposition and use for developing dynamic programming algorithms. Courcelle's meta-theorem and related results, logics MSO1 and MSO2.

Clique-width. Basic definitions and examples. The meta-theorem of Courcelle-Makowsky-Rotics. An example of using k-expressions to develop a dynamic programming algorithm.

References:

The course is based on several sources (books and research articles). The following is a list of some relevant literature:

 T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, second edition. McGraw-Hill, 2001.

 M. R. Garey, D. S. Johnson, Computers and Intractability: A guide to the theory of NP-Completeness, 1979.

 M. C. Golumbic. Algorithmic Graph Theory and Perfect Graphs, Volume 57 in the series Annals of Discrete Mathematics. North Holland, second edition, 2004.  A. Brandstädt, V. B. Le, J. P. Spinrad. Graph Classes: A Survey. SIAM, 1999.

 V. V. Vazirani. Approximation Algorithms, Springer-Verlag, 2001.

 J. A. Bondy, U. S. R. Murty. Graph Theory, North-Holland, Springer-Verlag, 2008.

 B. Korte, J. Vygen. Combinatorial Optimization. Theory and Algorithms, Volume 21 in the series Algorithms and Combinatorics, Springer-Verlag, druga izdaja, 2002.  R. Diestel, Graph Theory. Springer, 2006.

 A. Schrijver, Combinatorial Optimization, Springer, 2003.

 various papers from theoretical computer science journals and conferences (such as

WG, SODA, STACS, ESA, MFCS, ICALP, ISAAC, COCOON, COCOA, STOC, FOCS, IWOCA, WADS, SWAT, FCT, TAMC etc.)