Curso Dr. Marcin Kamiński

ALGORITHMIC GRAPH THEORY

 
Instructor: Marcin Kamiński, Département d’Informatique, Université Libre de Bruxelles, Belgium, Marcin.Kaminski@ulb.ac.be
Language of instruction: English

Course description

This course is an introduction to advanced topics in algorithmic graph theory. It focuses on design of efficient algorithms for hard graphtheoretic problems in classes of instances on which structural restrictions have been imposed. We will see how to turn combinatorial properties of graphs in such classes into efficient algorithms. We assume basic knowledge (undergraduate level) of graph theory and complexity theory. We will review the basics and present classic results but the emphasis will be placed on current research in the area with both the theory and applications in mind.

Course structure

  1. What algorithms are efficient?
    1. Polynomial-time algorithms (1hr)
    2. Approximation algorithms (1hr)
    3. Fixed-parameter tractable algorithms (1hr)
  2. Forbidding (induced) subgraphs
    1. Classes of graphs obtained by forbidding induced subgraphs (3hrs)
    2. Strong Perfect Graph Theorem (1hr)
    3. Structural theorems for claw-free graphs (1hr)
    4. Clique-width (1hr)
  3. Topological restrictions
    1. Planar graphs (2hrs)
    2. Graphs embeddable on surfaces (1hr)
    3. Tree-width (1hr)
    4. Theory of graph minors (2hrs)
 
There will be five 3-hour lectures.
Lecture 1: 1(a)-(c)
Lecture 2: 2(a)
Lecture 3: 2(b)-(d)
Lecture 4: 3(a)-(b)
Lecture 5: 3(c)-(d) 
 
Grading. The final grade will be based on a homework assignment to be completed after the course and sent to the instructor by email.

Previous edition of the course

For the previous edition of the course (including slides) visit: http://rutcor.rutgers.edu/mkaminski/AGTcourse

Bibliography

[1] Hans L. Bodlaender, Treewidth: Structure and Algorithms, SIROCCO 2007, 11 – 25 
[2] Andreas Brandstädt, Van Bang Le, and Jeremy P. Spinrad, Graph Classes: A Survey (Monographs on Discrete Mathematics and Applications), Society for Industrial Mathematics, 1987 
[3] Maria Chudnovsky and Paul Seymour, The Structure of Claw-free Graphs, Surveys in Combinatorics 2005, London Math. Soc. Lecture Note Series Vol. 327, 153 – 171 
[4] Bruno Courcelle and Stephan Olariu, Upper Bounds to the Clique-Width of Graphs, Discrete Applied Mathematics 101 (1997), 77–114 
[5] Martin Charles Golumbic, Algorithmic Graph Theory and Perfect Graphs, Volume 57, Second Edition (Annals of Discrete Mathematics), Elsevier, 2004 
[6] Rolf Niedermeier, Invitation to Fixed Parameter Algorithms, (Oxford Lecture Series in Mathematics and Its Applications), Oxford University Press, 2006 
[7] Paul Seymour, How the proof of the strong perfect graph conjecture was found, Gazette des Mathematiciens 109 (2006), 69 – 83.