Testing first-order properties for subclasses of sparse graphs
From MaRDI portal
Abstract: We present a linear-time algorithm for deciding first-order (FO) properties in classes of graphs with bounded expansion, a notion recently introduced by Nesetril 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 Nesetril and Ossona de Mendez on the existence of low tree-depth colorings.
Recommendations
Cited in
(67)- FO model checking on geometric graphs
- From \(\chi\)- to \(\chi_p\)-bounded classes
- Polynomial treedepth bounds in linear colorings
- Uniform orderings for generalized coloring numbers
- Classes of graphs with low complexity: the case of classes with bounded linear rankwidth
- Structural sparsity of complex networks: bounded expansion in random models and real-world graphs
- On the number of cliques in graphs with a forbidden minor
- Grad and classes with bounded expansion. II: Algorithmic aspects
- Modeling limits in hereditary classes: reduction and application to trees
- Bounds on half graph orders in powers of sparse graphs
- Colouring and covering nowhere dense graphs
- A dynamic data structure for MSO properties in graphs with bounded tree-depth
- Linear time low tree-width partitions and algorithmic consequences
- Deciding first-order properties of locally tree-decomposable structures
- Coloring and covering nowhere dense graphs
- Hyperbolic families and coloring graphs on surfaces
- Completeness for first-order properties on sparse structures with algorithmic applications
- Completeness for first-order properties on sparse structures with algorithmic applications
- Faster decision of first-order graph properties
- scientific article; zbMATH DE number 1405654 (Why is no real title available?)
- Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness
- First-order interpretations of bounded expansion classes
- Reducing CMSO model checking to highly connected graphs
- Recovering sparse graphs
- Test dense subgraphs in sparse uniform hypergraph
- Elimination Distance to Bounded Degree on Planar Graphs
- Progressive algorithms for domination and independence
- Algorithmic properties of sparse digraphs
- Data-compression for parametrized counting problems on sparse graphs
- Domination above \(r\)-independence: does sparseness help?
- Enumerating answers to first-order queries over databases of low degree
- First-order queries on classes of structures with bounded expansion
- First-order interpretations of bounded expansion classes
- Empirical evaluation of approximation algorithms for generalized graph coloring and uniform quasi-wideness
- Improved bounds for centered colorings
- Large independent sets in triangle-free planar graphs
- Algorithms for classes of graphs with bounded expansion
- On the Number of Cliques in Graphs with a Forbidden Subdivision or Immersion
- Erdös-Hajnal properties for powers of sparse graphs
- An algorithmic meta-theorem for graph modification to planarity and FOL
- On low rank-width colorings
- On the generalised colouring numbers of graphs that exclude a fixed minor
- A distributed low tree-depth decomposition algorithm for bounded expansion classes
- Lacon-, Shrub- and Parity-Decompositions: Characterizing Transductions of Bounded Expansion Classes
- Three-coloring triangle-free graphs on surfaces. VI: 3-colorability of quadrangulations
- Dominating set is fixed parameter tractable in claw-free graphs
- Elimination distance to bounded degree on planar graphs preprint
- Discrepancy and sparsity
- Counting subgraphs in somewhere dense graphs
- Nowhere dense classes of graphs
- Treelike decompositions for transductions of sparse graphs
- Extremal number of cliques of given orders in graphs with a forbidden clique minor
- Sunflowers meet sparsity: a linear-vertex kernel for weighted clique-packing on sparse graphs
- Decomposition horizons and a characterization of stable hereditary classes of graphs
- Twin-width. VIII: Delineation and win-wins
- Elementary first-order model checking for sparse graphs
- An algorithmic meta-theorem for graph modification to planarity and FOL
- Compound logics for modification problems
- Twin-width. IV: Ordered graphs and matrices
- Fine-grained meta-theorems for vertex integrity
- Twin-width of graphs on surfaces
- Advances in algorithmic meta theorems (invited paper)
- Linear colorings of graphs
- First order logic on pathwidth revisited again
- Compactors for parameterized counting problems
- Sublinear separators, fragility and subexponential expansion
- On low tree-depth decompositions
This page was built for publication: Testing first-order properties for subclasses of sparse graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5395732)
