The complexity of the problem of deciding properties expressible in FO logic on graphs -- the FO model checking problem (parameterized by the respective FO formula), is well-understood on so-called sparse graph classes, but much less understood on hereditary dense graph classes. Regarding the latter, a recent concept of twin-width [Bonnet et al., FOCS 2020] appears to be very useful. For instance, the question of these authors [CGTA 2019] about where is the exact limit of fixed-parameter tractability of FO model checking on permutation graphs has been answered by Bonnet et al. in 2020 quite easily, using the newly introduced twin-width. We prove that such exact characterization of hereditary subclasses with tractable FO model checking naturally extends from permutation to circle graphs (the intersection graphs of chords in a circle). Namely, we prove that under usual complexity assumptions, FO model checking of a hereditary class of circle graphs is in FPT if and only if the class excludes some permutation graph. We also prove a similar excluded-subgraphs characterization for hereditary classes of interval graphs with FO model checking in FPT, which concludes the line a research of interval classes with tractable FO model checking started in [Ganian et al., ICALP 2013]. The mathematical side of the presented characterizations -- about when subclasses of the classes of circle and permutation graphs have bounded twin-width, moreover extends to so-called bounded perturbations of these classes.
翻译:在图表中,FO逻辑(FO模型核对问题(以各自的FO公式为参数)所显示的特性的确定问题的复杂性,在所谓的稀薄图表类上被很好地理解,但在遗传稠密图形类上却更不为人理解。关于后者,最近对双曲线[Bonnet等人,FOSC 2020]的概念似乎非常有用。例如,这些作者的问题[CGTA 20199],即FO模型对变异图形的固定参数校准精确限度是2020年Bonnet等人的回答非常容易的,使用新引入的双宽等级。我们证明,对具有可移动式FO模型检查的遗传子类的精确定性,从变换换到圆形图(圆圈中交汇的交汇图)。 也就是说,根据通常的复杂假设,FOFO模型对遗传图类的侧边端校验的精确度是FPTT值,如果班级排除了某类的定调和等。我们还证明,在FO(FP)的数学分级中,这些分级的数学分级与FP(FO)的模型和分级的分级的分级中,这些分级与FOFO。