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

lmcs:9013 - Logical Methods in Computer Science, June 6, 2023, Volume 19, Issue 2 - https://doi.org/10.46298/lmcs-19(2:14)2023
Lacon-, Shrub- and Parity-Decompositions: Characterizing Transductions of Bounded Expansion ClassesArticle

Authors: Jan Dreier

    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.


    Volume: Volume 19, Issue 2
    Published on: June 6, 2023
    Accepted on: April 29, 2023
    Submitted on: January 28, 2022
    Keywords: Computer Science - Discrete Mathematics,Computer Science - Logic in Computer Science

    Consultation statistics

    This page has been seen 954 times.
    This article's PDF has been downloaded 169 times.