COMP5940M Graph Theory: Structure and Algorithms

15 creditsClass Size: 40

Module manager: Professor Kristina Vuskovic
Email: k.vuskovic@leeds.ac.uk

Taught: Semester 2 View Timetable

Year running 2019/20

Pre-requisite qualifications

COMP3931 Graph Algorithms and Complexity Theory
OR
MATH3033 Graph Theory
or equivalent

This module is not approved as an Elective

Module summary

Graph theory is a branch of mathematics that interfaces strongly with computer science. It developed enormously in recent decades due to its important applications in diverse areas such as transportation, telecommunication, molecular biology, industrial engineering, linguistics, chemistry, etc. Understanding structural properties of graphs is fundamental for the design of efficient algorithms. This module introduces students to main techniques and results from structural graph theory and considers their algorithmic applications. It covers classical results and more recent ones, and introduces current research techniques. This is a self-contained module; all necessary concepts and results used will be introduced and proved inside the module.

Objectives

To introduce students to some of the main techniques used to study the structure of graphs, and show how this leads to design of efficient algorithms.
On completion of this module, students should be able to:
- Prove classical results covered by the module;
- Understand the role of decompositions in graph-theoretic proofs and in algorithms on graphs;
- Be familiar with the decomposition by clique cut-sets and tree-decompositions ;
-Recognize how the methods learned can be extended and used to solve other problems.

Learning outcomes
On completion of the year/programme students should have provided evidence of being able to:
-to demonstrate in-depth, specialist knowledge and mastery of techniques relevant to the discipline and/or to demonstrate a sophisticated understanding of concepts, information and techniques at the forefront of the discipline;
-to exhibit mastery in the exercise of generic and subject-specific intellectual abilities;
-to demonstrate a comprehensive understanding of techniques applicable to their own research or advanced scholarship;
-proactively to formulate ideas and hypotheses and to develop, implement and execute plans by which to evaluate these;
-critically and creatively to evaluate current issues, research and advanced scholarship in the discipline.

Syllabus

Vertex colouring (greedy colouring heuristic, Brook’s Theorem, graphs with large chromatic numbers, Dizac’s Theorem, Hadwiger’s Conjecture)
Perfect Graphs (perfection of bipartite graphs, line graphs of bipartite graphs, perfect graph theorem.)
Chordal graphs (Lexicographic breadth-first search and recognition of chordal graphs, decomposition method and fast algorithms for colouring, clique and independent set problems)
Series parallel graphs
Tree decompositions (dynamic programming over tree decomposition).

Teaching methods

 Delivery type Number Length hours Student hours Lectures 22 1.00 22.00 Class tests, exams and assessment 1 2.00 2.00 Tutorial 10 1.00 10.00 Private study hours 116.00 Total Contact hours 34.00 Total hours (100hr per 10 credits) 150.00

Private study

Taught session prep: 33 hours
Taught session follow-up: 33 hours
Self-directed study: 9 hours
Assessment activities: 40 hours

Opportunities for Formative Feedback

Attendance and formative coursework.

Methods of assessment

Coursework
 Assessment type Notes % of formal assessment Assignment Written work 10.00 Assignment Written work 10.00 Assignment Written work 10.00 Assignment Written work 10.00 Total percentage (Assessment Coursework) 40.00

This module is re-assessed by exam only.

Exams
 Exam type Exam duration % of formal assessment Standard exam (closed essays, MCQs etc) 2 hr 00 mins 60.00 Total percentage (Assessment Exams) 60.00

This module is re-assessed by exam only.