BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:An Algorithmic Metatheorem for Directed Treewidth - Mateus de Oliv
 eria Oliveira\, KTH\, Stockholm
DTSTART:20141107T140000Z
DTEND:20141107T150000Z
UID:TALK55907@talks.cam.ac.uk
CONTACT:Jonathan Hayman
DESCRIPTION:The notion of directed treewidth was introduced by Johnson\, R
 obertson\, Seymour and Thomas [Journal of Combinatorial Theory\, Series B\
 , Vol 82\, 2001] as a first step towards an algorithmic metatheory for dig
 raphs. They showed that some NP-complete properties such as Hamiltonicity 
 can be decided in polynomial time on digraphs of constant directed treewid
 th. Nevertheless\, despite more than one decade of intensive research\, th
 e list of hard combinatorial problems that are known to be solvable in pol
 ynomial time when restricted to digraphs of constant directed treewidth ha
 s remained scarce. In this work we enrich this list by providing for the f
 irst time an algorithmic metatheorem connecting the monadic second order l
 ogic of graphs to directed treewidth. We show that most of the known posit
 ive algorithmic results for digraphs of constant directed treewidth can be
  reformulated in terms of our metatheorem. Additionally\, we show how to u
 se our metatheorem to provide polynomial time algorithms for two classes o
 f combinatorial problems that have not yet been studied in the context of 
 directed width measures. More precisely\, for each fixed k and w in N\, we
  show how to count in polynomial time on digraphs of directed treewidth w\
 ,  the number of minimum spanning strong subgraphs that are the union of k
  directed paths\, and the number of maximal subgraphs that are the union o
 f k directed paths and satisfy a given minor closed property. To prove our
  metatheorem we devise two technical tools which we believe to be of indep
 endent interest. First\, we introduce the notion of tree-zig-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-saturated tree 
 slice language\, a new formalism for the specification and manipulation of
  infinite sets of digraphs. \n
LOCATION:Room FW26\, Computer Laboratory\, William Gates Building
END:VEVENT
END:VCALENDAR