Graph Theory

Course guarantor:

Lecturer:

Tutor:

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, basics of graph theory.

Syllabus of lectures:

1.Havel's theorem, DFS tree, 2-connectivity and its characterization, an algorithm for finding bridges, an algorithm for finding strongly connected components.

2. Networks, flows in networks, Ford-Fulkerson algorithm, k-Connectedness, Ford-Fulkerson theorem, Menger's theorem,

3. Finding matching in bipartite graphs, Hall's theorem and its corollaries, finding matching in general graphs

4. Planar graphs, planar drawing, Euler's formula and its corollaries, Kuratowski's theorem and further considerations about planarity, dual of a plane graph, multigraphs, drawing on general surfaces

5. Graph coloring, first-fit algorithm, Five Color theorem, coloring of graphs on general surfaces, Mycielski's construction, perfect and chordal graphs, list coloring and choosability, edge coloring.

6. Finding all-pairs distance, Floyd-Warshall algorithm, using Dijkstra's algorithm, Fibonacci heaps, (a,b)-trees, B-trees, universal hashing.

7. Eulerian graphs, cycle space of a graph, Hamiltonian graphs, Traveling Salesperson problem, approximation algorithms.

8. Algorithms of computational geometry, convex envelope, sweep-line.

9. Linear algebra in combinatorics, number of spanning trees

10. Ramsey theory, introduction to probabilistic method, extremal combinatorics

11. Algorithms for special graph classes, minors and their algorithmic usage

12. Path and tree decompositions and basic properties, dynamic programming on tree decompositions, MSOL, Courcelle Theorem, tree-width of planar graphs and algorithms for planar graphs, bidimensionality

13. Baker's shifting technique, decompositions of dense graphs

Syllabus of tutorials:

Study Objective:

Overview of modern methods of graph theory.

Study materials:

1. Lecture notes for BIE-AG2 and NIE-GAK.

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/

No time-table has been prepared for this course

The course is a part of the following study plans:

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