Deciding First-Order Properties of Nowhere Dense Graphs

DOI10.1145/3051095zbMath1426.68172arXiv1311.3899OpenAlexW2625266575MaRDI QIDQ4640289

Stephan Kreutzer, Sebastian Siebertz, Martin Grohe

Publication date: 17 May 2018

Published in: Journal of the ACM, Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1311.3899

zbMATH Keywords

nowhere dense graphsalgorithmic graph structure theoryfirst-order model-checking

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Specification and verification (program logics, model checking, etc.) (68Q60) Structural characterization of families of graphs (05C75) Decidability of theories and sets of sentences (03B25) Descriptive complexity and finite models (68Q19) Games on graphs (graph-theoretic aspects) (05C57) Density (toughness, etc.) (05C42)

Related Items (92)

Tractability in constraint satisfaction problems: a survey ⋮ Compactors for parameterized counting problems ⋮ Characterising bounded expansion by neighbourhood complexity ⋮ Enumeration for FO Queries over Nowhere Dense Graphs ⋮ On ultralimits of sparse graph classes ⋮ Vapnik-Chervonenkis dimension and density on Johnson and Hamming graphs ⋮ On the parameterized complexity of reconfiguration of connected dominating sets ⋮ Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension ⋮ FO model checking on geometric graphs ⋮ Modeling limits in hereditary classes: reduction and application to trees ⋮ Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs ⋮ Quantified conjunctive queries on partially ordered sets ⋮ Coloring and Covering Nowhere Dense Graphs ⋮ Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs ⋮ Courcelle's theorem for triangulations ⋮ Parameterized complexity of graph burning ⋮ Reconfiguration on nowhere dense graph classes ⋮ Unnamed Item ⋮ Harmless sets in sparse classes ⋮ On the complexity of various parameterizations of common induced subgraph isomorphism ⋮ Kernelization and approximation of distance-\(r\) independent sets on nowhere dense graphs ⋮ On coloring numbers of graph powers ⋮ Fixed-parameter tractable distances to sparse graph classes ⋮ Quantified Conjunctive Queries on Partially Ordered Sets ⋮ Parameterized extension complexity of independent set and related problems ⋮ Towards a characterization of universal categories ⋮ Some lower bounds in parameterized \(\mathrm{AC}^{0}\) ⋮ Induced subdivisions and bounded expansion ⋮ Grouped domination parameterized by vertex cover, twin cover, and beyond ⋮ First-order Logic with Connectivity Operators ⋮ First-order limits, an analytical perspective ⋮ Grouped domination parameterized by vertex cover, twin cover, and beyond ⋮ Computing dense and sparse subgraphs of weakly closed graphs ⋮ On low tree-depth decompositions ⋮ Shallow Minors, Graph Products, and Beyond-Planar Graphs ⋮ Lacon-, Shrub- and Parity-Decompositions: Characterizing Transductions of Bounded Expansion Classes ⋮ SAT backdoors: depth beats size ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Bounds on half graph orders in powers of sparse graphs ⋮ Grundy Coloring and friends, half-graphs, bicliques ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the generalised colouring numbers of graphs that exclude a fixed minor ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ 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 ⋮ Successor-Invariant First-Order Logic on Classes of Bounded Degree ⋮ First-Order Model-Checking in Random Graphs and Complex Networks ⋮ Model checking existential logic on partially ordered sets ⋮ A gentle introduction to applications of algorithmic metatheorems for space and circuit classes ⋮ Reducing CMSO model checking to highly connected graphs ⋮ On the complexity of broadcast domination and multipacking In digraphs ⋮ On the weak 2-coloring number of planar graphs ⋮ Reconfiguration on sparse graphs ⋮ On the generalised colouring numbers of graphs that exclude a fixed minor ⋮ Maximum Shallow Clique Minors in Preferential Attachment Graphs Have Polylogarithmic Size ⋮ Parameterized Complexity of Graph Burning ⋮ A meta-theorem for distributed certification ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Complexity of token swapping and its variants ⋮ Unnamed Item ⋮ On low rank-width colorings ⋮ On the parameterized complexity of \([1,j\)-domination problems] ⋮ The parameterized complexity of \(k\)-edge induced subgraphs ⋮ A distributed low tree-depth decomposition algorithm for bounded expansion classes ⋮ Faster Existential FO Model Checking on Posets ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ EXISTENCE OF MODELING LIMITS FOR SEQUENCES OF SPARSE STRUCTURES ⋮ Elimination Distance to Bounded Degree on Planar Graphs ⋮ On the Parameterized Complexity of [1,j-Domination Problems] ⋮ Uniformly Automatic Classes of Finite Structures ⋮ Colouring and Covering Nowhere Dense Graphs ⋮ Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness ⋮ Structural sparsity of complex networks: bounded expansion in random models and real-world graphs ⋮ Lossy Kernels for Connected Dominating Set on Sparse Graphs ⋮ Digraphs of Bounded Width ⋮ Twin-width and polynomial kernels ⋮ Erdös--Hajnal Properties for Powers of Sparse Graphs ⋮ A meta-theorem for distributed certification ⋮ Improved Hardness of Maximum Common Subgraph Problems on Labeled Graphs of Bounded Treewidth and Bounded Degree ⋮ Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness

Uses Software

• SuLQ

Cites Work

• Efficient algorithms for privately releasing marginals via convex relaxations
• The Geometry of Differential Privacy: The Small Database and Approximate Cases
• Faster Algorithms for Privately Releasing Marginals
• Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
• Privately Releasing Conjunctions and the Statistical Query Barrier
• On the geometry of differential privacy
• Interactive privacy via the median mechanism
• The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
• Lower Bounds in Differential Privacy
• Iterative Constructions and Private Data Release
• Characterizing the sample complexity of private learners
• Faster private release of marginals on small databases
• Bounds on the Sample Complexity for Private Learning and Private Data Release
• Differential Privacy and the Fat-Shattering Dimension of Linear Queries
• Our Data, Ourselves: Privacy Via Distributed Noise Generation
• New Efficient Attacks on Statistical Disclosure Control Mechanisms
• Collusion-secure fingerprinting for digital data
• On the complexity of differentially private data release
• Advances in Cryptology – CRYPTO 2004
• Answering n _{2+o(1)} counting queries with differential privacy is hard
• Theory of Cryptography
• Unnamed Item
• Unnamed Item

This page was built for publication: Deciding First-Order Properties of Nowhere Dense Graphs