First-Order Model Checking on Structurally Sparse Graph Classes
From MaRDI portal
Abstract: A class of graphs is structurally nowhere dense if it can be constructed from a nowhere dense class by a first-order transduction. Structurally nowhere dense classes vastly generalize nowhere dense classes and constitute important examples of monadically stable classes. We show that the first-order model checking problem is fixed-parameter tractable on every structurally nowhere dense class of graphs. Our result builds on a recently developed game-theoretic characterization of monadically stable graph classes. As a second key ingredient of independent interest, we provide a polynomial-time algorithm for approximating weak neighborhood covers (on general graphs). We combine the two tools into a recursive locality-based model checking algorithm. This algorithm is efficient on every monadically stable graph class admitting flip-closed sparse weak neighborhood covers, where flip-closure is a mild additional assumption. Thereby, establishing efficient first-order model checking on monadically stable classes is reduced to proving the existence of flip-closed sparse weak neighborhood covers on these classes - a purely combinatorial problem. We complete the picture by proving the existence of the desired covers for structurally nowhere dense classes: we show that every structurally nowhere dense class can be sparsified by contracting local sets of vertices, enabling us to lift the existence of covers from sparse classes.
Cited in
(14)- On solution discovery via reconfiguration
- A polynomial Ramsey statement for bounded VC-dimension
- On classes of bounded tree rank, their interpretations, and efficient sparsification
- Solving a family of multivariate optimization and decision problems on classes of bounded expansion
- Graph theory. Abstracts from the workshop held January 5--10, 2025
- Decomposition horizons and a characterization of stable hereditary classes of graphs
- Data reduction for directed feedback vertex set on graphs without long induced cycles. Three rules to rule them all
- Model checking disjoint-paths logic on topological-minor-free graph classes
- Elementary first-order model checking for sparse graphs
- Subchromatic numbers of powers of graphs with excluded minors
- Extension preservation on dense graph classes
- Advances in algorithmic meta theorems (invited paper)
- Evaluating first-order formulas in structured graphs (invited talk)
- Elimination distance to dominated clusters
This page was built for publication: First-Order Model Checking on Structurally Sparse Graph Classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6425726)
