Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2104.10446 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929241238536192 |
|---|---|
| author | Dreier, Jan |
| author_facet | Dreier, Jan |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2104_10446 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Lacon-, Shrub- and Parity-Decompositions: Characterizing Transductions of Bounded Expansion Classes Dreier, Jan Discrete Mathematics Logic in Computer Science 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. |
| title | Lacon-, Shrub- and Parity-Decompositions: Characterizing Transductions of Bounded Expansion Classes |
| topic | Discrete Mathematics Logic in Computer Science |
| url | https://arxiv.org/abs/2104.10446 |