Graphs & Algorithms

Pavol Hell

Abstract

We investigate the boundary between computationally hard and easy graph theoretic problems, in the framework of constraint satisfaction problems and homomorphisms, as well as matchings and their generalizations. The role of special structure in the input graphs is highlighted, focusing on cases where the structure allows for certifying algorithms.