Deciding first-order properties of locally tree-decomposable structures
<|reference_start|>Deciding first-order properties of locally tree-decomposable structures: We introduce the concept of a class of graphs, or more generally, relational structures, being locally tree-decomposable. There are numerous examples of locally tree-decomposable classes, among them the class of planar graphs and all classes of bounded valence or of bounded tree-width. We also consider a slightly more general concept of a class of structures having bounded local tree-width.   We show that for each property P of structures that is definable in first-order logic and for each locally tree-decomposable class C of graphs, there is a linear time algorithm deciding whether a given structure A in C has property P. For classes C of bounded local tree-width, we show that for every k\ge 1 there is an algorithm that solves the same problem in time O(n^{1+(1/k)}) (where n is the cardinality of the input structure).<|reference_end|>
@article{frick2000deciding,
    title={Deciding first-order properties of locally tree-decomposable structures},
    author={Markus Frick and Martin Grohe},
    journal={arXiv preprint arXiv:cs/0004007},
    year={2000},
    archivePrefix={arXiv},
    eprint={cs/0004007},
    primaryClass={cs.DS cs.CC cs.DB}
}