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, NP-complete and NP-hard problems
- they are able to apply their knowledge to a variety of graph problems
- they can recall NP-hardness and NP-completeness 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 NP-hard 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 2-colourability versus 3-colourability. 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 NP-complete and NP-hard problems, and deal with many examples. Polynomial reductions will be treated in detail, again with many illustrative examples and exercises. For some NP-hard 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 NP-hard problems become easy when restricted to graph classes, like tree-like 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 NP-hard problems that remain NP-hard, even when restricted to very special graph classes.
|
 |
|