BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Isaac Newton Institute Seminar Series
SUMMARY:Logical Methods in the Complexity Analysis of Grap
h Algorithms - Kreutzer\, S (Technische Universitt
Berlin)
DTSTART;TZID=Europe/London:20120327T113000
DTEND;TZID=Europe/London:20120327T123000
UID:TALK37191AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/37191
DESCRIPTION:A classical observation in complexity theory is th
at many common algorithmic problems on graphs are
hard to solve. Consequently\, much work has gone i
nto studying restricted classes of admissible inpu
ts on which tractability results can be retained.
A particular rich source of structural properties
which guarantee the existence of efficient algorit
hms for many problems on graphs come from structur
al graph theory\, especially algorithmic graph min
or theory. It has been found that most generally h
ard problems become tractable on graph classes of
bounded tree-width and many remain tractable on pl
anar graphs or graph classes excluding a fixed min
or.\n\nBesides many specific results giving algori
thms for individual problems\, of particular inter
est are results that establish tractability of a l
arge class of problems on specific classes of inst
ances. 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 lo
gic to describe algorithmic problems and then esta
blish general tractability results for all problem
s definable in that logic on specific classes of i
nputs. These results are usually referred to as al
gorithmic meta-theorems.\n\nIn some sense the firs
t theorem of this form is Courcelle's famous resul
t that all monadic second-order definable problems
are solvable in linear time on all classes of str
uctures of bounded tree-width. Subsequently many f
urther theorems of this form and many tools for ob
taining such results have been developed.\n\nIn th
is tutorial we will present the main methods and r
esults obtained in this area. In the first part\,
the focus will be on logical tools that can be use
d to obtain algorithmic meta-theorems.\nIn the sec
ond part of the tutorial we will focus on methods
to establish corresponding lower bounds\, i.e. int
ractability results for particular logics on class
es of graphs that do not have any of the nice prop
erties that make algorithmic meta-theorems possibl
e. In particular\, we will present a reasonably ti
ght lower bound for Courcelle's theorem mentioned
above.\n
LOCATION:Seminar Room 1\, Newton Institute
CONTACT:Mustapha Amrani
END:VEVENT
END:VCALENDAR