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:Logic and Semantics Seminar (Computer Laboratory)
SUMMARY:An Algorithmic Metatheorem for Directed Treewidth
- Mateus de Oliveria Oliveira\, KTH\, Stockholm
DTSTART;TZID=Europe/London:20141107T140000
DTEND;TZID=Europe/London:20141107T150000
UID:TALK55907AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/55907
DESCRIPTION:The notion of directed treewidth was introduced by
Johnson\, Robertson\, Seymour and Thomas [Journal
of Combinatorial Theory\, Series B\, Vol 82\, 200
1] as a first step towards an algorithmic metatheo
ry for digraphs. They showed that some NP-complete
properties such as Hamiltonicity can be decided i
n polynomial time on digraphs of constant directed
treewidth. Nevertheless\, despite more than one d
ecade of intensive research\, the list of hard com
binatorial problems that are known to be solvable
in polynomial time when restricted to digraphs of
constant directed treewidth has remained scarce. I
n this work we enrich this list by providing for t
he first time an algorithmic metatheorem connectin
g the monadic second order logic of graphs to dire
cted treewidth. We show that most of the known pos
itive algorithmic results for digraphs of constant
directed treewidth can be reformulated in terms o
f our metatheorem. Additionally\, we show how to u
se our metatheorem to provide polynomial time algo
rithms for two classes of combinatorial problems t
hat have not yet been studied in the context of di
rected width measures. More precisely\, for each f
ixed k and w in N\, we show how to count in polyno
mial time on digraphs of directed treewidth w\, t
he number of minimum spanning strong subgraphs tha
t are the union of k directed paths\, and the numb
er of maximal subgraphs that are the union of k di
rected paths and satisfy a given minor closed prop
erty. To prove our metatheorem we devise two techn
ical tools which we believe to be of independent i
nterest. First\, we introduce the notion of tree-z
ig-zag number of a digraph\, a new directed width
measure that is at most a constant times directed
treewidth. Second\, we introduce the notion of z-s
aturated tree slice language\, a new formalism for
the specification and manipulation of infinite se
ts of digraphs. \n
LOCATION:Room FW26\, Computer Laboratory\, William Gates Bu
ilding
CONTACT:Jonathan Hayman
END:VEVENT
END:VCALENDAR