
Apart from the main aim to provide the students with a general understanding of the different aspects involved in the analysis of algorithmic solutions to graph problems, the specific learning goals of the course are that at the end of the course:
 the students can apply the basic notions of the analysis of algorithms and their computational complexity to a variety of graph problems
 they can explain the difference between polynomial, NPcomplete and NPhard problems
 they are able to apply their knowledge to a variety of graph problems
 they can recall NPhardness and NPcompleteness proofs from the lectures
 they can develop new proofs for variants of the treated problems
 they can recall structural properties of special graph classes
 they can analyse the complexity of graph problems restricted to such classes
 they can evaluate the quality of heuristics for NPhard problems
 they are able to apply their knowledge to analyse the quality of heuristics
 they can develop their own heuristics


In this course the focus is on graph problems for which an algorithmic solution is sought, and the difficulty and efficiency of the solution concepts. We will treat algorithmic solutions at a high level of abstraction, without programming code.
We start by introducing and addressing some seemingly analogous graph problems, like finding a shortest path versus a longest path between two given vertices, finding an Euler tour versus a Hamilton cycle, and testing a graph for 2colourability versus 3colourability. This should evoke the intuition that some graph problems are easy to solve algorithmically, whereas the analogous counterparts seem much harder to solve. We will formalize “easy” and “hard” by introducing the time complexity of an algorithm and the Big Oh notation, and define what is meant by a polynomial algorithm. We will distinguish solutions that are easy to find and that are easy to verify, as a means to define the classes P and NP in an intuitive way, avoiding the introduction of Turing Machines or other models of computation. We will also introduce NPcomplete and NPhard problems, and deal with many examples. Polynomial reductions will be treated in detail, again with many illustrative examples and exercises. For some NPhard problems, we will analyse possible heuristics for producing reasonable solutions, and for proving guaranteed quality measures. A large part of the remaining lectures and tutorials will deal with special graph classes. The motivation is that many NPhard problems become easy when restricted to graph classes, like treelike graphs, planar graphs, interval graphs, and others. We will supply examples in which such classes appear naturally from application areas. We will also look at NPhard problems that remain NPhard, even when restricted to very special graph classes.




 VoorkennisBasic knowledge in algorithms and graph theory, as in Module 7 of the current CS/AM Bachelor programme. 
Master Applied Mathematics 
  Verplicht materiaalLiteratureWritten and provided by the lecturer 

 Aanbevolen materiaalWerkvormenToetsenTest


 