Lacon-, Shrub- and Parity-Decompositions: Characterizing Transductions of Bounded Expansion Classes

DOI10.46298/LMCS-19(2:14)2023arXiv2104.10446MaRDI QIDQ6135763FDOQ6135763

Jan Dreier

Publication date: 26 August 2023

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

Abstract: The concept of bounded expansion provides a robust way to capture sparse graph classes with interesting algorithmic properties. Most notably, every problem definable in first-order logic can be solved in linear time on bounded expansion graph classes. First-order interpretations and transductions of sparse graph classes lead to more general, dense graph classes that seem to inherit many of the nice algorithmic properties of their sparse counterparts. In this paper, we show that one can encode graphs from a class with structurally bounded expansion via lacon-, shrub- and parity-decompositions from a class with bounded expansion. These decompositions are useful for lifting properties from sparse to structurally sparse graph classes.

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

zbMATH Keywords

first-order logicinterpretationsbounded expansiontransductions

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Cites Work

• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Title not available (Why is that?)
• Deciding First-Order Properties of Nowhere Dense Graphs
• Sparsity. Graphs, structures, and algorithms
• Title not available (Why is that?)
• Title not available (Why is that?)
• Deciding first-order properties of locally tree-decomposable structures
• Strong computational lower bounds via parameterized complexity
• Title not available (Why is that?)
• Colouring graphs with bounded generalized colouring number
• Orderings on graphs and game coloring number
• Algorithmic uses of the Feferman-Vaught theorem
• Fixed-parameter tractability, definability, and model-checking
• Testing first-order properties for subclasses of sparse graphs
• First-Order Interpretations of Bounded Expansion Classes
• On the number of types in sparse graphs
• On low tree-depth decompositions
• A New Perspective on FO Model Checking of Dense Graph Classes
• Coloring and Covering Nowhere Dense Graphs
• Twin-width I: Tractable FO Model Checking
• Uniform orderings for generalized coloring numbers
• First-Order Model-Checking in Random Graphs and Complex Networks
• Title not available (Why is that?)

Cited In (1)

• Bounding generalized coloring numbers of planar graphs using coin models

This page was built for publication: Lacon-, Shrub- and Parity-Decompositions: Characterizing Transductions of Bounded Expansion Classes

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