Graphs, Algorithms and a tiny bit of Logic
Stephan Kreutzer ( Oxford University Computing Laboratory )

16:30 29th April 2008 ( week 2, Trinity Term 2008 )Lecture Theatre A
In this talk we look at algorithmic problems on graphs, such as finding a vertex cover of a graph, or determining whether
the graph can be coloured by three colours so that no edge has both endpoints coloured in the same way. Such problems have
numerous applications in computer science, but in general many of these problems are NPhard, i.e. are unlikely to be efficiently
solvable on the class of all graphs.
Much effort has therefore been devoted to finding classes of graphs which on the one hand are general enough to allow interesting applications but on the other hand are restricted enough so that relevant problems can be solved efficiently. A typical example are planar graphs, which, for instance, are a useful model for road or railway maps and on which many problems that are intractable in general can be solved efficiently. Other interesting structural properties of graphs are the treewidth of graphs or other measures coming out of the graph minor theory.
In this talk we will give an introduction to this line of research. We will introduce the relevant structure properties of graphs, such as treewidth, and present some algorithms designed to work on graphs of small treewidth. The main focus will be on algorithmic metatheorems which are results that explain good algorithmic properties for a large class of problems at once. Many of these metatheorems are based on logical definability of algorithmic problems.
No prior knowledge of graph theory or logic is required, as all relevant methods will be properly defined and motivated.
Much effort has therefore been devoted to finding classes of graphs which on the one hand are general enough to allow interesting applications but on the other hand are restricted enough so that relevant problems can be solved efficiently. A typical example are planar graphs, which, for instance, are a useful model for road or railway maps and on which many problems that are intractable in general can be solved efficiently. Other interesting structural properties of graphs are the treewidth of graphs or other measures coming out of the graph minor theory.
In this talk we will give an introduction to this line of research. We will introduce the relevant structure properties of graphs, such as treewidth, and present some algorithms designed to work on graphs of small treewidth. The main focus will be on algorithmic metatheorems which are results that explain good algorithmic properties for a large class of problems at once. Many of these metatheorems are based on logical definability of algorithmic problems.
No prior knowledge of graph theory or logic is required, as all relevant methods will be properly defined and motivated.