Testing first-order properties for subclasses of sparse graphs
Testing first-order properties for subclasses of sparse graphs
复制标题
测试稀疏图子类的一阶属性
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
R. Thomas
中科院分区：
文献类型：
--
作者：
Zdenek Dvorák;D. Král;R. Thomas
我们提出了一个线性时间算法来决定一阶（FO）性质的类图有界扩展，最近推出的Nešetzanil和Ossona德门德斯的概念。这推广了文献中的几个结果，因为许多自然类的图有界扩张：有界树宽的图，所有真小闭图类，有界度的图，没有子图同构于固定图的细分的图，以及可以在固定曲面上绘制的图，使得每条边至多与常数个其他边相交。我们推出，有一个几乎线性时间的算法来决定FO性质的类图的局部有界的扩张。
更一般地说，我们设计了一个动态的数据结构，属于一个固定类的有界扩展的图形。在线性时间初始化之后，数据结构允许我们在恒定时间内测试FO属性，并且数据结构可以在添加/删除边之后在恒定时间内更新，前提是要添加的可能边的列表是预先已知的，并且它们的同时添加导致类中的图。我们的所有结果也适用于关系结构，并且基于Nešetzil和Ossona de Mendez关于低树深度着色存在的开创性结果。
We present a linear-time algorithm for deciding first-order (FO) properties in classes of graphs with bounded expansion, a notion recently introduced by Nešetřil and Ossona de Mendez. This generalizes several results from the literature, because many natural classes of graphs have bounded expansion: graphs of bounded tree-width, all proper minor-closed classes of graphs, graphs of bounded degree, graphs with no subgraph isomorphic to a subdivision of a fixed graph, and graphs that can be drawn in a fixed surface in such a way that each edge crosses at most a constant number of other edges. We deduce that there is an almost linear-time algorithm for deciding FO properties in classes of graphs with locally bounded expansion.
More generally, we design a dynamic data structure for graphs belonging to a fixed class of graphs of bounded expansion. After a linear-time initialization the data structure allows us to test an FO property in constant time, and the data structure can be updated in constant time after addition/deletion of an edge, provided the list of possible edges to be added is known in advance and their simultaneous addition results in a graph in the class. All our results also hold for relational structures and are based on the seminal result of Nešetřil and Ossona de Mendez on the existence of low tree-depth colorings.