Computer Science – Discrete Mathematics
Scientific paper
2011-09-23
Computer Science
Discrete Mathematics
Scientific paper
We present a linear-time algorithm for deciding first-order logic (FOL) properties in classes of graphs with bounded expansion, a notion recently introduced by Nesetril and Ossona de Mendez. 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 FOL 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 FOL 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 Nesetril and Ossona de Mendez on the existence of low tree-depth colorings.
Dvořák Zdeněk
Kral Daniel
Thomas Robin
No associations
LandOfFree
Testing first-order properties for subclasses of sparse graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Testing first-order properties for subclasses of sparse graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Testing first-order properties for subclasses of sparse graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-724182