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
|
|
|
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 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, and introduce NP-complete and NP-hard problems, avoiding the introduction of Turing Machines or other models of computation. The latter form a central part of the mathematically more rigorous approach in “Limits to Computing”. Polynomial reductions will be treated in detail, with many illustrative examples and exercises. For NP-hard problems, we will analyse possible heuristics for producing reasonable solutions, and for proving guaranteed quality measures, showing that some NP-hard problems allow good approximations, whereas others do not. 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.
|
 |
|