BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Logical Methods in the Complexity Analysis of Graph Algorithms - K
 reutzer\, S (Technische Universitt Berlin)
DTSTART:20120326T103000Z
DTEND:20120326T113000Z
UID:TALK37094@talks.cam.ac.uk
CONTACT:Mustapha Amrani
DESCRIPTION:A classical observation in complexity theory is that many comm
 on algorithmic problems on graphs are hard to solve. Consequently\, much w
 ork has gone into studying restricted classes of admissible inputs on whic
 h tractability results can be retained. A particular rich source of struct
 ural properties which guarantee the existence of efficient algorithms for 
 many problems on graphs come from structural graph theory\, especially alg
 orithmic graph minor theory. It has been found that most generally hard pr
 oblems become tractable on graph classes of bounded tree-width and many re
 main tractable on planar graphs or graph classes excluding a fixed minor.\
 n\nBesides many specific results giving algorithms for individual problems
 \, of particular interest are results that establish tractability of a lar
 ge class of problems on specific classes of instances. These results come 
 in various flavours. In this tutorial we will focus on results that take a
  descriptive approach\, i.e. results that use a logic to describe algorith
 mic problems and then establish general tractability results for all probl
 ems definable in that logic on specific classes of inputs. These results a
 re usually referred to as algorithmic meta-theorems.\n\nIn some sense the 
 first theorem of this form is Courcelle's famous result that all monadic s
 econd-order definable problems are solvable in linear time on all classes 
 of structures of bounded tree-width. Subsequently many further theorems of
  this form and many tools for obtaining such results have been developed.\
 n\nIn this tutorial we will present the main methods and results obtained 
 in this area. In the first part\, the focus will be on logical tools that 
 can be used to obtain algorithmic meta-theorems.\nIn the second part of th
 e tutorial we will focus on methods to establish corresponding lower bound
 s\, i.e. intractability results for particular logics on classes of graphs
  that do not have any of the nice properties that make algorithmic meta-th
 eorems possible. In particular\, we will present a reasonably tight lower 
 bound for Courcelle's theorem mentioned above.\n
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR