Jakub Gajarský, First-order interpretations of bounded expansion classes

Room B232 IBS (기초과학연구원)

The notion of bounded expansion captures uniform sparsity of graph classes and renders various algorithmic problems that are hard in general tractable. In particular, the model-checking problem for first-order logic is fixed-parameter tractable over such graph classes. With the aim of generalizing such results to dense graphs, we introduce classes of graphs with structurally bounded expansion, defined as first-order interpretations of

Jakub Gajarský, Model Checking on Interpretations of Classes of Bounded Local Clique-Width

Zoom ID: 869 4632 6610 (ibsdimag)

The first-order model checking problem for finite graphs asks, given a graph G and a first-order sentence $\phi$ as input, to decide whether $\phi$ holds on G. Showing the existence of an efficient algorithm for this problem implies the existence of efficient parameterized algorithms for various commonly studied problems, such as independent set, distance-r dominating

IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.