Graphs and Algorithms

This course introduces graph complexity parameters that, when bounded, allow to solve NP-hard problems. After quickly reviewing classical parameters and why they
Master of Science in Computer Science - International Track4 are not enough to measure hardness of interesting problems, we introduce some families of graphs and polynomial-time algorithms, when reduced to these graph classes, for notorious NP-hard problems. The objective is to highlight how specific structures can help in solving hard problems. In the second part, we introduce the notion of parameterized complexity and some key features for studying the fine-grained complexity of problems. For case study, we will introduce the notion of tree-width and some techniques for quickly solving, by dynamic programming, a bunch of NP-hard problems appearing in several areas such as in Databases, graphs, compilers, biology, etc. We will also survey bi-dimensionality theory. A last part will focus on applications (representing data, register allocation, query evaluation, etc.).