Outline

• Solving hard problems on special graphs
  why NP-hard problems have efficient solutions on special graphs, e.g. colourability or independent set on interval graphs, on trees, and on chordal graphs in a more general setting
  
• Tree decompositions of graphs
  four distinct (and equivalent) views of graph tree-width, some other "tree-shaped" decompositions
  
• Efficient algorithms on tree-shaped decompositions
  independent set, matching enumeration, EMSO problems, etc
  
• Minors in graphs
  the Graph Minors theorem of Robertson and Seymour, and efficient algorithms (just a very short outline)
  

Goals

This lecture briefly outlines the following algorithmic phenomenon - many NP-hard problems can be efficiently solved if we restrict the input to graphs of certain global structure, usually to be "tree-shaped" in a particular sense. Such an input structure allows to apply the dynamic programming paradigm and obtain more efficient algorithms. Moreover, this topic is very closely related to a deep theory of graph minors, one of the deepest parts of modern discrete mathematics.

 

Generally, the additional topics are not covered at all by the course textbook, and only online materials are presented.

Alternative book: [Reinhard Diestel: Graph Theory, electronic edition 2005]

Study in section 12 of the book (quite advanced reading, though).

Further study: Interested students can take the subject MA052 at FI, focused on interesting advanced chapters in structural graph theory, i.e. extending all the topics of this lecture.

Briefly showing an example of a tree-decomposition of the depicted graph.

The three-element bags of the decomposition are shown below, together with a colourful illustration of the interpolation property.