Cover Image

Elementary first-order model checking for sparse graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Gajarský, Jakub, Pilipczuk, Michał, Sokołowski, Marek, Stamoulis, Giannos, Toruńczyk, Szymon
Format:	Preprint
Published:	2024
Subjects:	Logic in Computer Science Discrete Mathematics Data Structures and Algorithms Combinatorics Logic
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Flipper games for monadically stable graph classes
by: Gajarský, Jakub, et al.
Published: (2023)

First-order transducibility among classes of sparse graphs
by: Gajarský, Jakub, et al.
Published: (2025)

Merge-width and First-Order Model Checking
by: Dreier, Jan, et al.
Published: (2025)

Maintaining $\mathsf{CMSO}_2$ properties on dynamic structures with bounded feedback vertex number
by: Majewski, Konrad, et al.
Published: (2021)

Graph classes through the lens of logic
by: Pilipczuk, Michał
Published: (2025)

On classes of bounded tree rank, their interpretations, and efficient sparsification
by: Gajarský, Jakub, et al.
Published: (2024)

3D-grids are not transducible from planar graphs
by: Gajarský, Jakub, et al.
Published: (2025)

Efficient reversal of transductions of sparse graph classes
by: Dreier, Jan, et al.
Published: (2026)

On merge-models
by: Buffière, Hector, et al.
Published: (2026)

Flip-width: Cops and Robber on dense graphs
by: Toruńczyk, Szymon
Published: (2023)

CNFs and DNFs with Exactly $k$ Solutions
by: Chandran, L. Sunil, et al.
Published: (2025)

Variants of Merge-Width and Applications
by: Drabik, Karolina, et al.
Published: (2026)

Separability Properties of Monadically Dependent Graph Classes
by: Bonnet, Édouard, et al.
Published: (2025)

Flip-Breakability: A Combinatorial Dichotomy for Monadically Dependent Graph Classes
by: Dreier, Jan, et al.
Published: (2024)

Foundations for an Abstract Proof Theory in the Context of Horn Rules
by: Lyon, Tim S., et al.
Published: (2023)

Solving Partial Dominating Set and Related Problems Using Twin-Width
by: Balabán, Jakub, et al.
Published: (2025)

Redundancy Is All You Need (for CSP Sparsification)
by: Brakensiek, Joshua, et al.
Published: (2024)

On first-order transductions of classes of graphs
by: Braunfeld, Samuel, et al.
Published: (2022)

On Numbers of Simplicial Walks and Equivalent Canonizations for Graph Recognition
by: Černý, Marek
Published: (2026)

Max Weight Independent Set in graphs with no long claws: An analog of the Gyárfás' path argument
by: Majewski, Konrad, et al.
Published: (2022)

Formal Primal-Dual Algorithm Analysis
by: Abdulaziz, Mohammad, et al.
Published: (2026)

Color Refinement for Relational Structures
by: Scheidt, Benjamin, et al.
Published: (2024)

The Iteration Number of the Weisfeiler-Leman Algorithm
by: Grohe, Martin, et al.
Published: (2023)

Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements
by: Grohe, Martin, et al.
Published: (2023)

Beyond Value Iteration for Parity Games: Strategy Iteration with Universal Trees
by: Koh, Zhuan Khye, et al.
Published: (2021)

SDPs and Robust Satisfiability of Promise CSP
by: Brakensiek, Joshua, et al.
Published: (2022)

Homomorphism Indistinguishability, Multiplicity Automata Equivalence, and Polynomial Identity Testing
by: Černý, Marek, et al.
Published: (2025)

Characterizations of monadically dependent tree-ordered weakly sparse structures
by: Buffière, Hector, et al.
Published: (2026)

Almost-linear time parameterized algorithm for rankwidth via dynamic rankwidth
by: Korhonen, Tuukka, et al.
Published: (2024)

First order distinguishability of sparse random graphs
by: Hershko, Tal, et al.
Published: (2024)

Coarse Balanced Separators in Fat-Minor-Free Graphs
by: Bonnet, Édouard, et al.
Published: (2026)

Faster diameter computation in graphs of bounded Euler genus
by: Kluk, Kacper, et al.
Published: (2025)

SAT Encoding of Partial Ordering Models for Graph Coloring Problems
by: Faber, Daniel, et al.
Published: (2024)

Smaller Circuits for Bit Addition
by: Goncharov, Mikhail, et al.
Published: (2025)

Epsilon-saturation for stable graphs and Littlestone classes
by: Malliaris, Maryanthe, et al.
Published: (2025)

Decomposition horizons and a characterization of stable hereditary classes of graphs
by: Braunfeld, Samuel, et al.
Published: (2022)

Designing sparse temporal graphs satisfying connectivity requirements
by: Bellitto, Thomas, et al.
Published: (2026)

Minor Containment and Disjoint Paths in almost-linear time
by: Korhonen, Tuukka, et al.
Published: (2024)

Asymptotically faster algorithms for recognizing $(k,\ell)$-sparse graphs
by: Deák, Bence, et al.
Published: (2026)

First-order logic axiomatization of metric graph theory
by: Chalopin, Jérémie, et al.
Published: (2022)