BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Model Checking Disjoint-Paths Logic on Topological-Minor-Free Grap
 h Classes - Giannos Stamoulis\, University of Montpellier
DTSTART:20230428T130000Z
DTEND:20230428T140000Z
UID:TALK199753@talks.cam.ac.uk
CONTACT:Jamie Vicary
DESCRIPTION:Disjoint-paths logic\, denoted FO+DP\, extends first-order log
 ic (FO) with\natomic predicates dp_k[(x_1\, y_1)\,…\,(x_k\, y_k)]\, expr
 essing the\nexistence of internally vertex-disjoint paths between x_i and 
 y_i\, for 1\n≤ i ≤ k. The formulas of FO+DP can be expressed in monadi
 c second-order\nlogic (MSO) and can capture problems that are not definabl
 e in FO. We\nfirst prove (fixed-parameter) tractability of the model check
 ing problem\nfor FO+DP on graph classes excluding some fixed graph as a mi
 nor. Then\,\nwe sketch how to extend this tractability result to graph cla
 sses\nexcluding some fixed graph as a *topological* minor. The latter sett
 les\nthe question of tractable model checking for this logic on\nsubgraph-
 closed graph classes\, since the problem is hard on\nsubgraph-closed class
 es not excluding a topological minor (assuming a\nfurther mild condition o
 f efficiency of encoding).\n\nJoint work with Petr A. Golovach and Dimitri
 os M. Thilikos and Nicole\nSchirrmacher\, Sebastian Siebertz\, Dimitrios M
 . Thilikos\, and Alexandre\nVigny.
LOCATION:SS03\, Computer Laboratory
END:VEVENT
END:VCALENDAR