First-order interpretations of bounded expansion classes

DOI10.1145/3382093MaRDI QIDQ5121280zbMATH OpenOpenAlexFDO

Authors Jakub Gajarský, Stephan Kreutzer, J. Nešetřil, P. Ossona de Mendez, Michał Pilipczuk, Sebastian Siebertz, Szymon Toruńczyk

Publication date 11 September 2020

Published in ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1810.02389, https://drops.dagstuhl.de/opus/volltexte/2018/9130/

zbMATH Keywords

bounded expansionfirst-order logiclogical interpretationsmodel-checkingsparse graph classes

Mathematics Subject Classification ID

Logic in computer science (03B70) Structural characterization of families of graphs (05C75) Specification and verification (program logics, model checking, etc.) (68Q60)

Abstract: The notion of bounded expansion captures uniform sparsity of graph classes and renders various algorithmic problems that are hard in general tractable. In particular, the model-checking problem for first-order logic is fixed-parameter tractable over such graph classes. With the aim of generalizing such results to dense graphs, we introduce classes of graphs with structurally bounded expansion, defined as first-order interpretations of classes of bounded expansion. As a first step towards their algorithmic treatment, we provide their characterization analogous to the characterization of classes of bounded expansion via low treedepth decompositions, replacing treedepth by its dense analogue called shrubdepth.

Recommendations

• First-order interpretations of bounded expansion classes
• Testing first-order properties for subclasses of sparse graphs
• First order properties on nowhere dense structures

Cited in

(31)

• From \(\chi\)- to \(\chi_p\)-bounded classes
• Clustering powers of sparse graphs
• scientific article; zbMATH DE number 3920432 (Why is no real title available?)
• First-order interpretations of bounded expansion classes
• Recovering sparse graphs
• Twin-width II: small classes
• Parameterized circuit complexity of model-checking on sparse structures
• Testing first-order properties for subclasses of sparse graphs
• Erdös-Hajnal properties for powers of sparse graphs
• Characterising graphs with no subdivision of a wheel of bounded diameter
• An extension of first order limit language
• Lacon-, Shrub- and Parity-Decompositions: Characterizing Transductions of Bounded Expansion Classes
• Transducing paths in graph classes with unbounded shrubdepth
• Discrepancy and sparsity
• Treelike decompositions for transductions of sparse graphs
• Stable graphs of bounded twin-width
• Model checking on interpretations of classes of bounded local cliquewidth
• Isomorphism for tournaments of small twin width
• Strong odd colorings in graph classes of bounded expansion
• Space-efficient parameterized algorithms on graphs of low shrubdepth
• A survey of degree-boundedness
• On first-order transductions of classes of graphs
• Twin-width. VIII: Delineation and win-wins
• Computing treedepth in polynomial space and linear FPT time
• Model checking disjoint-paths logic on topological-minor-free graph classes
• Elementary first-order model checking for sparse graphs
• Compound logics for modification problems
• Subchromatic numbers of powers of graphs with excluded minors
• First-order transductions of graphs (invited talk)
• Advances in algorithmic meta theorems (invited paper)
• Rainbow independent sets on dense graph classes

This page was built for publication: First-order interpretations of bounded expansion classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5121280)