Introduction to algorithmic graph theory and parameterised complexity
Kitty Meeks, University of Glasgow
Each morning session will be based around lecture-style teaching, but with significant opportunities
for student interaction and discussion. The afternoon sessions will include time for students to tackle
exercises individually or in small groups.
Day 1: Graphs, networks and modelling
An introduction to the basic definitions of graph theory, and an exploration of the applications of
graphs and how they can be used to model a wide variety of real-world datasets
Day 2: Optimisation with graphs
Some classic optimisation problems on graphs, and algorithms to solve them – including tractable
problems such as minimum spanning tree and NP-complete problems such as graph colouring.
Day 3: Classical intractability
NP-completeness in more detail, polynomial reductions, and the practical implications of NP-
Day 4: Coping with intractability
An overview of coping strategies including approximation algorithms, heuristics, and parameterised
Day 5: Basics of parameterised complexity
Examples of NP-complete problems that admit efficient parameterised algorithms, some basic
techniques in the design of such algorithms, and the notion of parameterised intractability.