Module manager: Dr Bogdan Alecu
Email: B.Alecu@leeds.ac.uk
Taught: Semester 2 (Jan to Jun) View Timetable
Year running 2024/25
Students must have studied one of the prerequisite modules below, or a module at an equivalent level. A solid mathematical foundation is desirable.
| COMP3940 | Graph Algorithms and Complexity Theory |
| MATH3033 | Graph Theory |
This module is not approved as a discovery module
Graphs are an extremely powerful tool for modelling real-world systems. They have applications in logistics, telecommunication, molecular biology, industrial engineering, linguistics, chemistry, and many other areas. However, many of the optimisation problems arising from these applications are computationally hard when there are no restrictions on the input. Thankfully, the scenarios that we aim to model often impose additional conditions on the structure of the corresponding graphs. This module focuses on how that structural information can be used to solve the relevant optimisation problems efficiently, with an emphasis on mathematical rigour.
This module aims to:
• motivate the study of graphs through examples of real-life inspired scenarios
• introduce the terminology required to talk about structural features of graphs
• illustrate a range of techniques for making use of these structural features
• provide an overview of the field, including some milestone results, as well as the guiding questions that led to them
• foster an appreciation of the mathematical way of thinking, and of the way it is applied to the study of graphs
On completion of the module, students should be able, in the context of working with graphs, to:
• understand and manipulate abstract concepts
• extract useful information from a complex system with many moving parts
• transform an intuitive, heuristic argument into a formal, rigorous one
• recognise faulty reasoning, and correct it
• identify structural features of graphs that are likely to yield good algorithmic behaviour
• use these structural features to design efficient algorithms for optimisation problems
• rigorously prove related results such as correctness of these algorithms
• wield various theoretical tools to derive these results
The main syllabus covers the following:
• the motivating example of interval graphs
• the terminology of hereditary classes, minimal forbidden induced subgraph characterisations, and graph parameters
• vertex colourings and the chromatic number
• comparability graphs
• chordal graphs
• basic Ramsey theory
• treewidth
Additional topics may be covered, such as perfect graphs, chi-boundedness, and graph decompositions.
| Delivery type | Number | Length hours | Student hours |
|---|---|---|---|
| Lectures | 22 | 1 | 22 |
| Tutorial | 11 | 1 | 11 |
| Private study hours | 117 | ||
| Total Contact hours | 33 | ||
| Total hours (100hr per 10 credits) | 150 | ||
There will be weekly problem classes, as well as a dedicated weekly office hour to support the module. In addition, there will be formative MCQs.
| Assessment type | Notes | % of formal assessment |
|---|---|---|
| Assignment | Coursework | 10 |
| Assignment | Coursework | 10 |
| Assignment | Coursework | 10 |
| Total percentage (Assessment Coursework) | 30 | |
This module is re-assessed by exam only.
| Exam type | Exam duration | % of formal assessment |
|---|---|---|
| Open Book exam | 2.0 Hrs 0 Mins | 70 |
| Total percentage (Assessment Exams) | 70 | |
This module is re-assessed by exam only.
The reading list is available from the Library website
Last updated: 9/25/2024
Errors, omissions, failed links etc should be notified to the Catalogue Team