2024/25 Taught Postgraduate Module Catalogue

COMP5940M Graph Theory: Structure and Algorithms

15 creditsClass Size: 40

Module manager: Dr Bogdan Alecu
Email: B.Alecu@leeds.ac.uk

Taught: Semester 2 (Jan to Jun) View Timetable

Year running 2024/25

Pre-requisite qualifications

Students must have studied one of the prerequisite modules below, or a module at an equivalent level. A solid mathematical foundation is desirable.

Pre-requisites

COMP3940	Graph Algorithms and Complexity Theory
MATH3033	Graph Theory

This module is not approved as an Elective

Module summary

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.

Objectives

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

Learning outcomes
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

Syllabus

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.

Teaching methods

Delivery type	Number	Length hours	Student hours
Lectures	22	1.00	22.00
Tutorial	11	1.00	11.00
Private study hours			117.00
Total Contact hours			33.00
Total hours (100hr per 10 credits)			150.00

Opportunities for Formative Feedback

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.

Methods of assessment

Coursework

Assessment type	Notes	% of formal assessment
Assignment	Coursework	10.00
Assignment	Coursework	10.00
Assignment	Coursework	10.00
Total percentage (Assessment Coursework)		30.00

This module is re-assessed by exam only.

Exams

Exam type	Exam duration	% of formal assessment
Open Book exam	2 hr 00 mins	70.00
Total percentage (Assessment Exams)		70.00

This module is re-assessed by exam only.

Reading list

The reading list is available from the Library website

Last updated: 29/04/2024 16:12:35

Disclaimer

Browse Other Catalogues

• Undergraduate module catalogue
• Taught Postgraduate module catalogue
• Undergraduate programme catalogue
• Taught Postgraduate programme catalogue

Errors, omissions, failed links etc should be notified to the Catalogue Team.PROD