Graph Theory

Garant předmětu:

Ondřej Suchý

Lecturer:

Ondřej Suchý, Tomáš Valla

Tutor:

Ondřej Suchý, Tomáš Valla

Supervisor:

Department of Theoretical Computer Science

Synopsis:

Attention will be paid both to structural issues and to questions of algorithmization and computational complexity of basic optimization problems restricted to special graph classes, aiming at determining the boundary between polynomially solvable and NP-hard variants of the problems.

Requirements:

General knowledge of discrete mathematics and efficient algorithms.

Syllabus of lectures:

1. Network Flows

2. Applications of network flows - higher connectivity of graphs, Ford-Fulkerson and Menger Theorem, Hall's Marriage Theorem

3. Matching in graphs

4. Planar graphs - Kuratowski Theorem, 5 Color Theorem

5. Chromatic number and colorings of graphs

6. Hamiltonian graphs

7. Minors and their algorithmic usage

8. Dynamic programming on trees and grids, path and tree decompositions and basic properties

9. Dynamic programming on tree decompositions

10. MSOL, Courcelle Theorem and an alternative characterization of tree width

11. Computing tree width, tree width of planar graphs and algorithms for planar graphs, bidimensionality

12. Baker's shifitng technique, decopositions of dense graphs

Syllabus of tutorials:

Study Objective:

Overview of modern methods of graph theory.

Study materials:

1. R. Diestel, Graph Theory, 5th edition, Springer, 2017.

2. Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh, Parameterized Algorithms, Springer 2015.

3. Downey, Rodney G., Fellows, Michael R.: Fundamentals of Parameterized Complexity, Springer, 2013.

Note:

Further information:

https://courses.fit.cvut.cz/PI-TGR/

Time-table for winter semester 2024/2025:

Time-table is not available yet

Time-table for summer semester 2024/2025:

Time-table is not available yet

The course is a part of the following study plans:

• Informatics (doctoral) (compulsory elective course)
• Informatics (compulsory elective course)