Abstract
We introduce the concept of a class of graphs 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 show that for each locally tree-decomposable class C of graphs and for each property ϕ of graphs that is definable in first-order logic, there is a linear time algorithm deciding whether a given graph G ∈ C has property ϕ.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
A.V. Aho, J.E. Hopcroft, and J.D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974.
S. Arnborg, J. Lagergren, and D. Seese. Easy problems for tree-decomposable graphs. Journal of Algorithms, 12:308–340, 1991.
A.V. Aho and J.D. Ullman. iThe universality of data retrieval languages. In Conference Record of the Sixth Annual ACM Symposium on Principles of Programming Languages, pages 110–120, 1979.
B.S. Baker. Approximation algorithms for NP-complete problems on planar graphs. Journal of the ACM, 41:153–180, 1994.
H.L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing, 25:1305–1317, 1996.
H.L. Bodländer. Treewidth: Algorithmic techniques and results. In I. Privara and P. Ruzicka, editors, Proceedings 22nd International Symposium on Mathematical Foundations of Computer Science, MFCS’97, volume 1295of Lecture Notes in Computer Science, pages 29–36. Springer-Verlag, 1997.
B. Courcelle. Graph rewriting: An algebraic and logic approach. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume 2, pages 194–242. Elsevier Science Publishers, 1990.
R.G. Downey and M.R. Fellows. Parametrized Complexity. Springer-Verlag, 1999.
R.G. Downey, M.R. Fellows, and U. Taylor. The parametrized complexity of relational database queries and an improved characterization of W[1]. In Bridges, Calude, Gibbons, Reeves, and Witten, editors, Combinatorics, Complexity, and Logic-Proceedings of DMTCS’ 96, pages 194–213. Springer-Verlag, 1996.
D. Eppstein. Subgraph isomorphism in planar graphs and related problems. In Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 632–640, 1995.
H. Gaifman. On local and non-local properties. In Proceedings of the Herbrand Symposium, Logic Colloquium’ 81. North Holland, 1982.
M.R. Garey, D.S. Johnson, and L. Stockmeyer. Some simplified NP-complete graph problems. Theoretical Computer Science, 1:237–267, 1976.
N. Immerman. Upper and lower bounds for first-order expressibility. Journal of Computer and System Sciences, 25:76–98, 1982.
C.H. Papadimitriou and M. Yannakakis. On the complexity of database queries. In Proceedings of the 16th ACM Symposium on Principles of Database Systems, pages 12–19, 1997.
D. Seese. Linear time computable problems and first-order descriptions. Mathematical Structures in Computer Science, 6:505–526, 1996.
M. Yannakakis. Perspectives on database theory. In Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science, pages 224–246, 1995.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Frick, M., Grohe, M. (1999). Deciding First-Order Properties of Locally Tree-Decomposable Graphs. In: Wiedermann, J., van Emde Boas, P., Nielsen, M. (eds) Automata, Languages and Programming. Lecture Notes in Computer Science, vol 1644. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48523-6_30
Download citation
DOI: https://doi.org/10.1007/3-540-48523-6_30
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66224-2
Online ISBN: 978-3-540-48523-0
eBook Packages: Springer Book Archive