一句话：提出模块分解定理，将图类可定义规范化归约到素图，证明带计数不动点逻辑在排列图上捕获多项式时间。
是否存在捕获多项式时间的逻辑是描述复杂性与数据库理论的核心公开问题。Grohe 曾证明带计数的不动点逻辑在排除子式的图类上捕获多项式时间。本文转而考虑排除诱导子图的图类，利用 Gallai 的模块分解，提出模块分解定理：将图类 C 的可定义规范化归约到其素图类的可定义规范化，其中素图用线性序集上的二元关系着色。应用该定理，作者证明带计数的不动点逻辑也在排列图上捕获多项式时间；并附带得到模块分解树可在对数空间计算，进而 cograph 识别与规范化也可在对数空间完成。
The question of whether there is a logic that captures polynomial time is one of the main open problems in descriptive complexity theory and database theory. In 2010 Grohe showed that fixed point logic with counting captures polynomial time on all classes of graphs with excluded minors. We now consider classes of graphs with excluded induced subgraphs. For such graph classes, an effective graph decomposition, called modular decomposition, was introduced by Gallai in 1976. The graphs that are non-decomposable with respect to modular decomposition are called prime. We present a tool, the Modular Decomposition Theorem, that reduces (definable) canonization of a graph class C to (definable) canonization of the class of prime graphs of C that are colored with binary relations on a linearly ordered set. By an application of the Modular Decomposition Theorem, we show that fixed point logic with counting also captures polynomial time on the class of permutation graphs. As a side effect of the Modular Decomposition Theorem, we further obtain that the modular decomposition tree is computable in logarithmic space. It follows that cograph recognition and cograph canonization is computable in logarithmic space.
DOI 原文 ·
@inproceedings{paperbot4148,
title = {Capturing polynomial time using Modular Decomposition},
author = {Berit Grussien},
booktitle = {LICS},
year = {2017},
doi = {10.1109/lics.2017.8005123}
}