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

DOI10.46298/LMCS-19(2:14)2023MaRDI QIDQ6135763zbMATH OpenFDO

Authors Jan Dreier

Publication date 26 August 2023

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

Copyright license Creative Commons Attribution 4.0 International

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)

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.

Recommendations

• First-order interpretations of bounded expansion classes
• First-order interpretations of bounded expansion classes
• Treelike decompositions for transductions of sparse graphs
• Testing first-order properties for subclasses of sparse graphs
• Algorithms for classes of graphs with bounded expansion

Cites work

• scientific article; zbMATH DE number 3819693 (Why is no real title available?)
• scientific article; zbMATH DE number 969067 (Why is no real title available?)
• scientific article; zbMATH DE number 3266604 (Why is no real title available?)
• Algorithmic uses of the Feferman-Vaught theorem
• Coloring and covering nowhere dense graphs
• Colouring graphs with bounded generalized colouring number
• Deciding first-order properties of locally tree-decomposable structures
• First-Order Model-Checking in Random Graphs and Complex Networks
• First-order interpretations of bounded expansion classes
• First-order logic with counting: at least, \textit{weak} Hanf normal forms always exist and can be computed!
• Fixed-parameter tractability, definability, and model-checking
• Logic, graphs, and algorithms
• On low tree-depth decompositions
• On the number of types in sparse graphs
• Orderings on graphs and game coloring number
• Sparsity. Graphs, structures, and algorithms
• Strong computational lower bounds via parameterized complexity
• Testing first-order properties for subclasses of sparse graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Twin-width. I: Tractable FO model checking
• Uniform orderings for generalized coloring numbers

Cited in

(3)

• Bounding generalized coloring numbers of planar graphs using coin models
• Space-efficient parameterized algorithms on graphs of low shrubdepth
• Treelike decompositions for transductions of sparse graphs

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)