2000/04/17 by Markus Frick, Frick, Markus, Martin Grohe +1 · 1 citation
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Databases (cs.DB) #F.1.3 #F.2.2 #FOS: Computer and information sciences #G.2.2 #H.2.4 #Interconnection Networks and Systems #cs.CC #cs.DB #cs.DS
paper · pdf · doi:10.48550/arxiv.cs/0004007
arxiv created 2000/04/17 · openalex publication_date 2000/04/17 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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≥ 1 there is an algorithm that solves the same problem in time O(n1+(1/k)) (where n is the cardinality of the input structure).