CloseHelpPrint
Kies de Nederlandse taal
Course module: 201900082
201900082
Graph Algorithms and Complexity
Course info
Course module201900082
Credits (ECTS)5
Course typeCourse
Language of instructionEnglish
Contact personprof.dr.ir. H.J. Broersma
E-mailh.j.broersma@utwente.nl
Lecturer(s)
Examiner
prof.dr.ir. H.J. Broersma
Lecturer
prof.dr.ir. H.J. Broersma
Contactperson for the course
prof.dr.ir. H.J. Broersma
Academic year2021
Starting block
1B
RemarksThe course is open to students from other programmes.
Application procedureYou apply via OSIRIS Student
Registration using OSIRISYes
Aims
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
Content
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.
Assumed previous knowledge
Basic knowledge in algorithms and graph theory, as in Module 7 of the current CS/AM Bachelor programme.
Participating study
Master Applied Mathematics
Participating study
Master Computer Science
Required materials
Literature
Written and provided by the lecturer
Recommended materials
-
Instructional modes
Lecture

Tutorial

Tests
Test

CloseHelpPrint
Kies de Nederlandse taal