Department Seminars & Colloquia

Category IBS-KAIST Seminar
Event Discrete Mathematics
Title Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes
Abstract The disjoint paths logic, FOL+DP,  is an extension of First Order Logic (FOL) with the extra atomic predicate $\mathsf{dp}_k(x_1,y_1,\ldots,x_k,y_k),$ expressing the existence of internally vertex-disjoint paths between $x_i$ and $y_i,$ for $i\in \{1,\ldots, k\}$. This logic can express a wide variety of problems that escape the expressibility potential of FOL. We prove that for every minor-closed graph class, model-checking for FOL+DP can be done in quadratic time. We also introduce an extension of FOL+DP, namely the scattered disjoint paths logic, FOL+SDP, where we further consider the atomic predicate $\mathsf{s-sdp}_k(x_1,y_1,\ldots,x_k,y_k),$ demanding that the disjoint paths are within distance bigger than some fixed value $s$. Using the same technique we prove that model-checking for FOL+SDP can be done in quadratic time on classes of graphs with bounded Euler genus. Joint work with Petr A. Golovach and Dimitrios M. Thilikos.
Daytime 2022-12-06 (Tue) / 16:30 ~ 17:30
Place Room B332, IBS (기초과학연구원)
Language English
Speaker`s name Giannos Stamoulis
Speakers`s Affiliation LIRMM, Université de Montpellier
Speaker`s homepage https://www.lirmm.fr/~gstamoulis/
Other information
Hosts Sang-il Oum
URL https://dimag.ibs.re.kr/event/2022-12-06/
담당자
연락처